백준 1637번 날카로운 눈은 여러 등차수열에 등장하는 수 가운데 홀수 번 등장하는 수와 그 횟수를 찾는 문제다. 그런 수가 없으면 NOTHING을 출력한다. 문제는 홀수 번 등장하는 수가 최대 하나라는 조건을 준다.
처음 풀 때는 검색의 도움도 받았지만, 누적 개수의 홀짝을 이용해 단절점을 찾는 방식으로 내 풀이를 다시 만들었다. 이 문제는 내 첫 Platinum 해결이어서 특히 기억에 남는다. 기쁜 마음과 별개로, 예전 code에는 경계값 초기화에서 overflow가 생길 수 있는 부분도 있었다. 이번에는 그 부분까지 다시 검증했다.
수열 하나가 x 이하에 몇 개를 만들까
입력 한 줄 A C B는 다음 등차수열을 뜻한다.
A, A+B, A+2B, ... (값이 C 이하인 동안)
x 이하의 항 개수는 두 경우로 나뉜다.
x < A이면 0개x >= A이면 마지막 범위를min(x, C)로 제한
count(A, C, B, x)
= (min(x, C) - A) / B + 1
모든 수열의 결과를 더한 누적 함수를 F(x)라고 하자.
F(x) = 모든 수열에서 x 이하인 항의 개수 합
예를 들어 한 수열이 1, 3, 5, 7이라면 다음과 같다.
| x | x 이하의 항 | 개수 |
|---|---|---|
| 0 | 없음 | 0 |
| 1 | 1 | 1 |
| 4 | 1, 3 | 2 |
| 7 | 1, 3, 5, 7 | 4 |
| 10 | 1, 3, 5, 7 | 4 |
한 수열의 개수를 O(1)에 계산하므로 F(x)는 O(N)에 구할 수 있다.
왜 누적 개수의 홀짝으로 위치를 찾을 수 있나
각 정수의 전체 등장 횟수를 생각해 보자. 짝수 번 등장한 수는 누적 합의 parity를 바꾸지 않는다. 홀수 번 등장한 수는 parity를 한 번 바꾼다.
문제에서 홀수 빈도의 수는 최대 하나라고 보장한다. 그 수를 k라고 하면 다음 관계가 성립한다.
x < k → F(x)는 짝수
x >= k → F(x)는 홀수
k를 지나며 그 수의 홀수 개가 누적 합에 추가되고, 이후 다른 수들은 모두 짝수 번씩 추가되므로 parity가 다시 바뀌지 않는다.
이 때문에 다음 predicate가 이분 탐색에 쓸 수 있는 단조 형태가 된다.
isOdd(x) = (F(x) % 2 == 1)
false false false ... true true true
↑
처음 true인 값이 k
여기서 홀수 빈도의 수가 최대 하나라는 보장이 중요하다. 홀수 빈도의 수가 여러 개라면 누적 parity가 false와 true 사이를 여러 번 오갈 수 있어 이 predicate로 일반적인 이분 탐색을 할 수 없다.
NOTHING을 먼저 판별한다
모든 입력 수열의 마지막 값 이상에서 F(x)는 전체 항 개수다. 탐색 상한을 가장 큰 C로 두면 F(maxC)로 충분하다.
F(maxC)가 짝수: 홀수 빈도의 수가 없으므로NOTHINGF(maxC)가 홀수: 홀수 빈도의 수가 하나 존재
이 결론도 “홀수 빈도의 수가 최대 하나”라는 조건 때문에 가능하다. 일반적인 multiset에서는 홀수 빈도의 서로 다른 수가 두 개 있어 전체 합이 짝수일 수도 있다.
첫 번째 홀수 누적 지점을 이분 탐색한다
탐색 구간은 입력 중 가장 작은 A부터 가장 큰 C까지다.
lo = min(A)
hi = max(C)
중간값 mid에서 F(mid)가 홀수라면 정답은 mid 또는 그보다 왼쪽에 있다. 짝수라면 정답은 오른쪽에 있다.
F(mid)가 홀수 → hi = mid
F(mid)가 짝수 → lo = mid + 1
lo == hi가 되면 처음으로 누적 개수가 홀수가 되는 정수다.
해당 정수의 실제 등장 횟수
F(k)는 k 이하의 전체 항 개수다. F(k-1)을 빼면 정확히 k인 항만 남는다.
frequency(k) = F(k) - F(k - 1)
이 차이는 문제 조건에 따라 홀수다.
Java 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
private static final class Sequence {
private final long start;
private final long end;
private final long step;
private Sequence(long start, long end, long step) {
this.start = start;
this.end = end;
this.step = step;
}
}
private static Sequence[] sequences;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
sequences = new Sequence[n];
long minStart = Long.MAX_VALUE;
long maxEnd = Long.MIN_VALUE;
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
long start = Long.parseLong(st.nextToken());
long end = Long.parseLong(st.nextToken());
long step = Long.parseLong(st.nextToken());
sequences[i] = new Sequence(start, end, step);
minStart = Math.min(minStart, start);
maxEnd = Math.max(maxEnd, end);
}
if ((countAtMost(maxEnd) & 1L) == 0L) {
System.out.println("NOTHING");
return;
}
long lo = minStart;
long hi = maxEnd;
while (lo < hi) {
long mid = lo + (hi - lo) / 2;
if ((countAtMost(mid) & 1L) == 1L) {
hi = mid;
} else {
lo = mid + 1;
}
}
long answer = lo;
long frequency = countAtMost(answer) - countAtMost(answer - 1);
System.out.println(answer + " " + frequency);
}
private static long countAtMost(long x) {
long total = 0L;
for (Sequence sequence : sequences) {
if (x < sequence.start) {
continue;
}
long last = Math.min(x, sequence.end);
total += (last - sequence.start) / sequence.step + 1;
}
return total;
}
}
예전 코드에서 고친 overflow
기존 풀이에는 최솟값 초기화가 다음처럼 작성돼 있었다.
long min = Integer.MAX_VALUE + 200000;
왼쪽 변수는 long이지만 덧셈의 두 operand가 모두 int다. 따라서 덧셈이 먼저 int로 계산되어 overflow가 난 뒤 그 잘못된 값이 long으로 변환된다.
int 계산에서 overflow
↓
음수 값이 만들어짐
↓
그 음수가 long으로 확장됨
이 문제에서는 탐색 하한이 불필요하게 음수로 넓어져도 우연히 답을 찾을 가능성이 있지만, 경계값 code로는 잘못됐다. 가장 작은 시작값을 구하려면 의미가 분명한 값을 사용한다.
long minStart = Long.MAX_VALUE;
중간값도 다음처럼 계산한다.
long mid = lo + (hi - lo) / 2;
(lo + hi) / 2보다 합의 overflow 가능성을 줄이는 형태다. 이 문제 입력은 양의 32-bit 정수 범위지만, countAtMost의 합은 여러 수열의 항 개수를 더하므로 long을 쓰는 편이 안전하다.
정확성 확인
풀이가 맞는 이유를 세 단계로 정리할 수 있다.
1. countAtMost(x)는 x 이하의 항을 정확히 센다
각 수열에서 x < start면 포함되는 항이 없다. 그렇지 않으면 start부터 min(x, end)까지 step 간격으로 존재하는 항의 수가 (last - start) / step + 1이다. 이를 모두 더하면 F(x)다.
2. 홀수 predicate는 정답을 경계로 단조롭게 바뀐다
정답보다 작은 값까지는 모든 정수의 빈도가 짝수이므로 누적 개수도 짝수다. 정답의 홀수 빈도가 추가된 뒤에는 나머지 정수의 빈도가 모두 짝수이므로 누적 개수는 계속 홀수다.
3. 이분 탐색은 첫 true를 찾는다
F(mid)가 홀수면 첫 true가 mid 이하에 있으므로 hi = mid, 짝수면 mid까지 정답이 없으므로 lo = mid + 1로 줄인다. 종료 시 lo == hi가 첫 true이며 홀수 빈도의 정수다.
마지막으로 F(answer) - F(answer - 1)이 그 정수의 등장 횟수를 정확히 구한다.
복잡도
F(x)를 계산할 때 모든 수열을 한 번씩 보므로 O(N)이다. 값 범위를 이분 탐색하므로 전체 시간 복잡도는 다음과 같다.
O(N log(maxC - minA + 1))
수열 정보를 저장하는 공간은 O(N)이다. 정수 범위 전체를 배열로 만들지 않기 때문에 값의 최댓값이 커도 범위 크기만큼 memory를 사용하지 않는다.
반례로 점검할 경계
홀수 빈도의 수가 없는 경우
2
1 3 1
1 3 1
1, 2, 3이 각각 두 번씩 등장하므로 NOTHING이다.
정답이 탐색 하한인 경우
3
1 1 1
2 4 1
2 4 1
1만 한 번 등장하고 나머지는 두 번씩 등장한다. 답은 1 1이다.
한 값이 세 번 등장하는 경우
3
4 4 1
4 4 1
4 4 1
답은 4 3이다. 단순히 존재 여부가 아니라 F(4) - F(3)으로 빈도까지 구해야 한다.
큰 경계값
입력을 int로 읽고 중간 계산만 long으로 바꾸면 parsing이나 덧셈에서 먼저 overflow가 날 수 있다. 처음부터 Long.parseLong과 long 연산을 사용한다.
이 문제에서 배운 것
이 문제의 이분 탐색 대상은 정렬된 배열의 원소가 아니다. F(x)의 홀짝이라는 predicate가 바뀌는 첫 지점이다. 매개 변수 탐색에서 중요한 것은 “값이 정렬돼 보이는가”보다 다음 두 가지다.
x가 주어졌을 때 predicate를 충분히 빠르게 계산할 수 있는가?- 그 predicate가 탐색 구간에서 false에서 true로 한 번만 바뀌는가?
첫 Platinum 해결이라는 기쁨도 컸지만, 다시 보니 더 오래 남은 것은 문제의 조건을 단조성으로 바꾸는 과정이었다. 그리고 맞았던 code라도 overflow와 경계값을 다시 읽어야 한다는 점도 함께 남았다.
참고 자료
'배움과 성장 > 알고리즘·문제풀이' 카테고리의 다른 글
| 백준 1707 Java: 이분 그래프를 BFS 2-Coloring으로 판별하기 (0) | 2022.06.15 |
|---|---|
| 백준 7569 Java: 3차원 토마토를 Multi-Source BFS로 풀기 (0) | 2022.05.30 |
| 백준 12015 Java: LIS 길이를 Lower Bound로 O(N log N)에 구하기 (0) | 2022.05.29 |
| 백준 24444·24445 Java: BFS 방문 순서와 인접 리스트 정렬 (0) | 2022.05.28 |
| 백준 24479·24480 Java: 재귀 없이 DFS 방문 순서 맞추기 (0) | 2022.05.24 |
댓글