본문 바로가기

PS/BOJ757

백준 16678 자바 - 모독 (BOJ 16678 JAVA) 문제 : boj16678 1. 문제 이해 결국 단 1번의 Defile로 모두 박탈시키려면 모든 의원의 명예를 1부터 차츰차츰 상승하는 계단형식으로 만들면 된다. 즉, 모든 의원의 명예가 낮은 명예부터 봤을 때 2이상 차이가 나지 않게 하면 된고, 이렇게 만들 때 최소한만 감소시켜서 진행해야 한다. 2. 문제 풀이 1부터 n까지 확인하면서 해당 값을 한명씩 무조건 가지도록 명예를 깎는다면 모든 명예값이 2이상 차이나지 않을 수 있다. 단순히 생각해도 더 낮은 숫자를 만들기 위해서는 애초에 명예가 낮은 의원의 명예를 깎는것이 더 최소한의 횟수로 만들 수 있을 것이다. 따라서 우선 입력으로 들어온 값을 오름차순으로 정렬해보자. 그리고 1부터 1개씩 증가시키며 해당 값에 한명 이상 매칭시켜보자. 예를들어 '예제.. 2022. 2. 21.
백준 18917 자바 - 수열과 쿼리 38 (BOJ 18917 JAVA) 문제 : boj18917 제거 연산이 '항상 A에 x가 있는 쿼리만 주어진다' 라는 조건이 있으므로 상당히 간단해지는 문제이다. 애초에 뭐 가장 앞에 있는걸 제거한다는 부분도 딱히 의미가 없다. 아무튼 있는 값에 대해서만 제거가 되므로 편하게 할 수 있다. 1. 모든 원소를 더한 값 sum과 같이 변수를 하나 두고 1 x 형태의 연산이 들어올 때 더해두고, 2 x 형태의 연산이 들어올 때 빼두면 된다. 2. 모든 원소를 XOR한 값 이게 좀 어려울 수 있다. 일단 1 x 형태의 연산은 그냥 XOR을 하면 된다. ('^' 연산)2 x 형태가 문제인데, 사실 이것도 그냥 XOR을 하면 된다. 왜냐면 어떠한 수 n에 대해 n^n = 0 이다. 즉 자기 자신을 빼내는 것 역시 XOR로 동일한 수를 진행하면 되는.. 2022. 2. 20.
백준 4351 자바 - Hay Points (BOJ 4351 JAVA) 문제 : boj4351 String으로 되어 있는 문자열과, 해당 항목에 대한 int를 저장할 수 있어야 한다. HashMap을 사용하면 효율적으로 저장하고, 찾을 수 있다. m개의 단어와 숫자를 받아 HashMap에 단어를 key, 숫자를 value로 저장한다. 그리고 n개를 입력받으면서 띄어쓰기를 기준으로 나누어 HashMap에 해당 단어가 있다면 점수를 더해나가면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Main { private void solution() throws Exception { BufferedReader br = new Bu.. 2022. 2. 19.
백준 18294 자바 - Biodiversity (BOJ 18294 JAVA) 문제 : boj18294 1. 우선 각 String마다 카운팅 할 수 있어야 한다. HashMap을 사용하면 편하게 할 수 있다. 2. 매번 각 String을 카운팅하면서, 그 중 현재까지 가장 큰 값과 가장 큰 값을 가지는 동물의 이름을 따로 저장해둔다. (혹은 마지막에 해시맵에서 key들을 뽑아낸 후 확인해도 된다.) 3. 다른 동물들의 합보다 어떠한 동물이 더 많으려면 (int)N/2보다 더 많은 수를 가져야 한다. (홀수라도 5/2 = 2 이므로 3 이상이면 더 많은것이다.) 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Main { private .. 2022. 2. 18.
백준 20291 자바 - 파일 정리 (BOJ 20291 JAVA) 문제 : boj20291 1. A.B 의 형태로 입력이 주어질 때, 결국 A는 아예 필요없고 B만 보면 된다. 따라서 문자열 파싱을 통해 '.' 뒤의 문자만 빼낼 수 있어야 한다. 2. 확장자에 대한 카운팅이 필요하다. 해시를 사용하는것이 효율적이다. 해시맵을 사용해 key를 확장자로 두고, value를 카운팅으로 하면 된다. 3. 결과를 확장자 이름순으로 출력해야 한다. 해시맵에서 keySet을 빼내서 정렬해도 되겠지만, 애초에 메모리를 좀 더 써서 따로 key값만 가지고 있다면 더 효율적으로 정렬할 수 있다. 내 경우엔 리스트에 새로운 key가 나올 경우 담아두었다. 그리고 리스트를 정렬한 후, 오름차순으로 정렬되어있는 key가 담긴 리스트를 순회하며 key와 value를 얻어 출력해줬다. 코드 : .. 2022. 2. 17.
백준 12927 자바 - 배수 스위치 (BOJ 12927 JAVA) 문제 : boj12927 얼핏 어렵게 볼 수 있지만, A번 스위치를 누를 경우 A의 배수들만 조정이 되는 것이므로 그냥 A가 낮은 순서대로 그리디하게 확인하면 된다. 즉, 1번부터 차례대로 볼 경우 A번 스위치가 'Y'라면 A+1이상의 스위치에서는 A번 스위치를 끌 수 있는 경우 자체가 없으므로 무조건 A번은 눌러야 하는 것이다. 그렇다고 그 뒤의 스위치를 먼저 누른 후에 그 이전 스위치를 누른다고 더 횟수가 줄어드는 경우도 존재하지 않는다. 따라서 단순하게 1번부터 차례대로 확인하면서 'Y'라면 그 뒤의 스위치가 어찌됬든 무조건 꺼나가면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class.. 2022. 2. 16.
백준 1339 자바 - 단어 수학 (BOJ 1339 JAVA) 문제 : boj1339 1. 그리디 문제이다. 대충봐도 어떠한 문자를 9~0 중 어떤걸 선택해야 하는지 파악해야 하는 문제이므로 그리디 문제임을 알 수 있다. 이 때, 단순히 자리수가 높다고 높은 수를 줘버리면 다음과 같은 반례를 통과할 수 없다. A가 가장 자리수가 높으므로 9를 주고, Z를 8을 주면 총 합은 1780이 된다. 하지만 A를 8, Z를 9로 하면 1790이 나오므로 Z를 9로 주는 것이 이득임을 알 수 있다. 10 AZZ ZZ ZZ ZZ ZZ ZZ ZZ ZZ ZZ ZZ 2. 해결 방법 각 자리수에 대해 가중치를 주는 방식으로 해결할 수 있다. 즉, 1의 자리에 나온 문자는 가중치 1, 10의 자리는 10, ... 이런식이다. 예를들어 '예제 입력 2'는 다음과 같이 표현할 수 있다. [.. 2022. 2. 15.
백준 11292 자바 - 키 큰 사람 (BOJ 11292 JAVA) 문제 : boj11292 각 TC마다 N개를 모두 입력받기 전에는 뭐를 출력해야할지 알 수 없다. 또한 입력이 들어온 순서를 유지해야 하므로 정렬해서 처리할 수도 없다. 그렇다면 전부 어딘가에 저장하면서 입력받는다. 이 때 입력받으면서 최대값을 확인한 후, 다시 순회하며 최대값에 부합하는 String을 출력해주면 된다. 이 경우 O(N+N)이 된다. 내 경우엔 ArrayList를 두고 최대값이 갱신되면 리스트를 초기화하는 방식을 택했다. 즉, 현재 최대값과 동일한 값이 들어오면 ArrayList에 String을 추가하고, 최대값보다 낮으면 무시하고, 최대값보다 크면 리스트를 초기화하고 현재 최대값도 갱신하면서 새로 만들어진 리스트에 String을 추가한다. 이 경우 O(N)이 된다. 메모리도 덜쓴다. 사.. 2022. 2. 14.
백준 14428 자바 - 수열과 쿼리 16 (BOJ 14428 JAVA) 문제 : boj14428 가장 간단하게 생각할 수 있는 방법인 brute force부터 확인해보자. 10만개의 N개가 주어지고, 모든 쿼리가 '2 1 100000' 이런식이라면 O(NM)이 필요할 것이다. 따라서 시간내에 통과할 수 없다. 사실 이런식으로 중간중간 값이 변경되고, 범위에 대한 쿼리를 출력하는 유형은 대표적으로 세그먼트 트리(segment tree)를 사용하는 문제이다. 내 경우엔 조금 더 비효율적이지만, 훨씬 간단하고 구현을 이해하기 편하다고 생각되는 sqrt decompositon 방식을 사용해서 풀어봤다. 1. Sqrt decomposition 초기화 (코드의 init 함수) 이론적으론 세그먼트 트리에 비해 이해하기가 엄청 간단하다. 특정 수열이 N개의 수를 가진다면 N의 제곱근만큼 .. 2022. 2. 13.
백준 6219 자바 - 소수의 자격 (BOJ 6219 JAVA) 문제 : boj6219 1. 우선 A, B 사이의 소수를 어떻게 효율적으로 구할까? 에라토스테네스의 체 방식을 사용하여 미리 구해두면 된다. 이 때 내 경우엔 좀 더 효율적으로 하고자 sqrt(n)까지만 확인(왜 그래도 되는지는 여기를 확인해보면 된다.)하고, 짝수는 굳이 안봐도 되므로 아예 확인하지 않는 등의 약간의 추가 처리가 들어가있다. 코드에서 getPn()을 확인해보면 된다. 2. 다음으로 어떠한 정수가 있을 때 해당 수에 숫자 D가 포함되는지 어떻게 알 수 있을까? 가장 간단하게는 해당 정수를 String으로 변환하고 숫자 D도 character로 변경해서 확인해보는 방법이 있다. 당연히 좀 비효율적이다. 좀 더 빠르게 하려면 나머지 연산과 나누기 연산을 사용하면 된다. 어떠한 n에 대해 n%.. 2022. 2. 12.

티스토리툴바