BOJ 1637번 날카로운 눈 자바(java) 풀이
문제 정리
- 정수가 여러 개 모여 있는 정수더미가 있다. 그 안에는 어떤 특정한 정수 하나만 홀수개 존재하고 나머지 정수는 짝수개 존재한다.
- 이 중에서 홀수개가 존재하는 정수를 찾아야한다.
- N은 1이상 20,000이하
- 그리고 N개의 줄에 걸쳐 세개의 숫자(A, C, B)가 주어진다. A, A+B, A+2B, A+3B...의 정수들이 정수더미 안에 있다. A+kB는 C보다 작거나 같다.
- 1 <= A,B,C <= 2,147,483,647
- 홀수개 존재하는 정수와 그 수가 몇개 있는지 출력한다. 홀수개인 정수가 없다면 NOTHING을 출력한다.
문제 접근
처음에는 배열로 하려했지만 배열로 21억개를 만드니까 역시나 생성이 되지 않았습니다.
그래서 HashMap을 이용하여 key에는 숫자를 넣고 value값으로 몇개 인지 적으려고 했습니다.
그러나 이도 되지 않았습니다. ㅠㅠㅠㅠ
그래서 어떻게 할지 고민하다가 힌트를 보고 누적 합을 이용하면 되겠구나 했습니다.
이렇게 하면 되겠구나는 생각했지만 어떻게 코딩할지 모르겠었습니다.
그리고 다른 분의 설명을 참고하여 간신히 이해했습니다...
문제 풀이
- 범위를 A[i]의 최솟값을 왼쪽 값, C[i]의 최댓값을 오른쪽 값으로 합니다.
- 중간 값을 구합니다. 그 중간 값까지의 누적합을 구합니다.
누적 합은 그 숫자까지 개수가 몇개있는지 계산합니다.
- 누적 합의 계산은 (min(mid, C[i]) -A[i] )/ B[i] +1로 구합니다.
3.1 mid와 C[i]중 작은 값을 찾는 이유는 c[i]가 10이고 mid가 15인 경우 mid를 끝 값으로 하면 C[i]와 mid 사이에 있는 없는 값이 계산에 더해질 수 있습니다.
3.2 A[i]를 빼는 이유는 다음과 같습니다. 끝 값에서 시작값을 빼서 구간의 길이를 구하기 위해서 입니다.
3.3 B[i]로 나누는 이유는 다음과 같습니다. 구간의 길이에서 더해지는 공차?의 값을 나누면 구간에서 수가 몇개 있는지 구할 수 있습니다. 예를들어 구간이 110이면 구간의 길이는 9이고 1씩 더해진다면 9/1=9입니다. 210까지 9개입니다.
3.4 거기에 1을 더하는 이유는 시작 값을 더하기 위해서입니다. 이렇게 하면 10이 됩니다.
- 중간에 홀수 개가 있는 정수 부터 누적 합이 홀수가 됩니다.
예제의 경우 2,2,2,3,2,2,2,2,2,2입니다
누적 합은 2,4,6,9,11,13,15,17,19,21 입니다.
보면 개수가 3인 곳 부터 누적합은 홀수가 됩니다.
이를 이용하여 이분탐색을 합니다.
- mid에서의 누적 합이 짝수라면 홀수인 정수가 오른쪽에 있음을 의미합니다. 만약 누적 합이 홀수라면 홀수개인 정수가 왼쪽에 있음을 의미합니다.
- 이분탐색이 끝나고 left인 값인 초기 right 값과 같다면 이는 찾지 못한 것이므로 NOTHING을 출력합니다. 그렇지 않다면 left가 그 홀수인 정수를 나타냅니다. 홀수인 정수의 개수는 getSum(left) - getSum(left -1)로 구할 수 있습니다.
백준 1637번 날카로운 눈 자바 코드