BOJ 1637 날카로운 눈
출처 : https://www.acmicpc.net/problem/1637
난이도 : 플레 4
풀이 날짜 : 2022-12-18
출처 : https://www.acmicpc.net/problem/1300
1차 풀이(HashMap) : 실패 (메모리초과)
풀이
HashMap<Integer, Integer>을 이용해서 나오는 숫자들을 저장하고 그 숫자들의 갯수들을 저장하는 것으로 문제를 해결하려고 하였다.
저장이 다 끝나면 keyset을 탐색해서 값이 홀수인 키를 찾아주면 된다고 생각하였다.
HashMap.get() 과 put()의 시간 복잡도는 O(1)이기 때문에 입력을 제외하고는 빠르게 N번 탐색하면 되기 때문에 시간 복잡도는 O(N)이다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.HashSet;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
int N = Integer.parseInt(br.readLine());
for(int i=0; i<N; i++) {
st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken());
int C = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
for(int j = A; j <= C; j += B) {
hm.put(j, hm.getOrDefault(j, 0) + 1);
}
}
br.close();
for(int i : hm.keySet()) {
if(hm.get(i) % 2 == 1) {
System.out.println(i + " " + hm.get(i));
return;
}
}
System.out.println("NOTHING");
}
}결과
결과 분석
메모리 초과가 발생하였다. 이는 문제의 조건이 원인이었다.
"A, B, C는 1보다 크거나 같고 2,147,483,647보다 작거나 같은 정수이다"
만약 A, B, C 가 1, 1, 2,147,483,647일 경우
HashMap의 키에는 1부터 2,147,483,647까지의 값들이 저장이 된다.
HashMap의 메모리 값은 4바이트로 4바이트 * 2,147,483,647 = 8.58993459GB이다.
이는 문제의 메모리 조건인
128MB를 넘어서게 된다.
이를 해결하기 위해서는 모든 수들을 저장하지 않는 방식으로 해결해야 한다.
2차 풀이(이분 탐색) : 성공
풀이
이분탐색
문제의 알고리즘 분류를 보니 이분 탐색이었다.
이 문제가 어떻게 이분탐색으로 풀 수 있는지 이해가 되지 않았으나 문제에서 답을 알 수 있었다. 홀수가 1개만 존재한다는 점이었다.
s부터 e까지의 범위의 숫자들의 갯수들의 합을 구할 수 있다면 짝수들로만 이루어지면 짝수, 홀수가 포함되어 있다면 홀수가 될 것이다.
즉 s부터 e까지 갯수들의 합이 홀수라면 s와 e사이에 찾는 수가 있는 것이다.
이를 통해 l과 r을 설정하고 mid를 이동해서 홀수인 수를 찾아준다,
숫자들의 갯수 합 구하는 방법
그렇다면 1부터 mid까지의 갯수들의 합을 어떻게 구할 수 있을까?
그것은 A, B, C 목록들을 돌아가면서 mid값을 비교하며 숫자를 세주면 된다.
A,B,C를 int[N][3]d에 저장함으로서 아까전에 메모리 초과 문제를 해결할 수 있다.
공간 복잡도 = 4바이트 * 20,000 * 3 = 240 KB
mid와 A,B,C를 비교해서 갯수들의 합을 구해주면 된다.
mid가 만약 A보다 작을 경우 A,B,C에는 mid보다 작거나 같은 수가 없다.
if(mid < A) continue;mid가 A보다 클 경우 A,B,C에는 mid보다 작은 수가 포함되어 있다.
mid와 C 둘 중에 작은 숫자에 - A를 빼주고 이 차를 B로 나눠주면 된다.
거기에 A는 포함되지 않았기에 1을 더해준다.
count += (Math.min(mid, C) - A) / B + 1;이렇게 mid보다 작거나 같은 갯수들의 합을 구할 수 있다.
이분 탐색
이제 합을 구할 수 있으니 이분탐색을 마저 완성시켜보자
mid의 갯수들의 합이 홀수인 경우 l과 mid 사이에 찾고자 하는 수가 있다. r을 이동시켜서 범위를 좁혀주자.
// count = mid보다 작거나 같은 숫자들의 갯수
if(count % 2 == 0)
r = mid;mid의 갯수들의 합이 짝수인 경우 mid와 r 사이에 찾고자 하는 수가 있다. l을 이동시켜서 범위를 좁혀주자.
// count = mid보다 작거나 같은 숫자들의 갯수
if(count % 2 == 1)
l = mid + 1;그렇다면 l과 r의 처음 범위를 생각해보자.
A, B, C 목록들을 받으면서 최소의 A가 l이고 최대의 C가 r이 될 것이다. 그 범위를 넘어서는 숫자는 필요하지 않다.
이렇게 이분탐색을 하고 나면 l은 결국 찾고자 하는 수가 될 것이다.
만약 홀수가 없다면 계속 l = mid+1이 되어 l = r(maxC)가 될 것이다.
이 maxC가 답일 경우도 있기 때문에 maxC의 갯수를 세줘야 한다.
입력 :
3
1 10 1
1 10 1
10 10 1
출력 :
10 3
갯수를 세주는 방법은 A, B, C 목록에 l(최종 l)을 비교해준다.
A, B, C 안에 l이 있으면 count를 세준다.
A + i * B = l이면 된다.
이는
(l-A) % B == 0 인지를 보면 된다.
int count = 0;
for(int i=0; i<N; i++){
int A = arr[i][0];
int B = arr[i][1];
int C = arr[i][2];
if((l-A) % B == 0)
count++;
}코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class No1637 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
int arr[][] = new int[N][3];
// l의 범위를 정하기 위한 A값의 최소를 저장할 곳
int minA = Integer.MAX_VALUE;
// r의 범위를 정하기 위한 C값의 최대를 저장할 곳
int maxC = 0;
// N줄에 걸쳐 A, C, B를 입력받는다.
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken());
int C = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
// A, B, C 저장
arr[i][0] = A;
arr[i][1] = B;
arr[i][2] = C;
// 최대 최소 기록하기
minA = Math.min(minA, A);
maxC = Math.max(maxC, C);
}
br.close();
long l = minA;
long r = maxC;
// 이분 탐색 시작
while (l < r) {
long mid = (l + r) / 2;
// A,B,C 목록들을 보면서 mid 보다 작은 숫자들의 갯수가 기록되는 곳
long count = 0;
// A,B,C 목록 돌기
for (int i = 0; i < N; i++) {
int A = arr[i][0];
int B = arr[i][1];
int C = arr[i][2];
if (mid < A) continue;
count += (Math.min(C, mid) - A) / B + 1;
}
// System.out.println(l + " " + mid + " " + count);
// count가 짝수이면 갯수가 홀수인 수는 mid에서 r사이에 있다.
if (count % 2 == 0) {
l = mid + 1;
}
// count가 홀수이면 갯수가 홀수인 수는 l과 mid사이에 있다.
else if (count % 2 == 1) {
r = mid;
}
}
// l의 갯수를 찾아줘야 한다.
// A + i * B == l일 경우를 세준다.
// 다만 l이 C보다 클 경우, A가 l보다 클 경우는 계산 X
// (l - A) % B == 0일 경우를 세준다.
long count = 0;
// A,B,C 목록 돌기
for (int i = 0; i < N; i++) {
int A = arr[i][0];
int B = arr[i][1];
int C = arr[i][2];
// 범위를 벗어난다면
if (C < l || l < A)
continue;
if ((l - A) % B == 0)
count++;
}
// maxN까지 갔을 경우 만약 maxN이 짝수이면 NOTHING이다.
if (l == maxC && count % 2 == 0) {
System.out.println("NOTHING");
} else {
System.out.println(l + " " + count);
}
}
}
결과
느낀점
이분탐색 풀이 문제라는 것을 알고나서도 이런 문제를 어떻게 이분탐색으로 풀지? 라고 생각될 정도로 생소한 문제였다.
하지만 이 문제와 유사한 문제들을 많이 경험해보는 걸로 확실한 풀이를 할 수 있도록 노력해야 할 것 같다.
