이번 문제는 백준의 골드 4 문제 합이 0 문제이다.
문제를 차근차근 읽어보자.
최대 10000명의 코딩 실력이 -10000 ~ 10000 사이의 정수로 주어진다.
이 때 합이 0이되는 3인 1조를 구성할 수 있는 경우의 수를 구해달라고 한다.
완전탐색?
우선 가장 간단하게 푸는 방법은 완전 탐색일 것이다.
3명을 모두 뽑아서 합이 0이 되는 경우를 모두 찾는 것이다.
하지만 이 부분은 시간복잡도에 문제가 있다.
3명을 모두 다 뽑아 본다는 것은 3중 for문을 의미한다.
즉, O(N^3)의 시간 복잡도를 갖는다는 얘기가 된다.
N이 현재 최대 10000까지 가능하기 때문에, 10000^3이 Worst case가 된다.
이는 1,000,000,000,000으로, 시간 초과가 발생할 수 밖에 없는 수가 된다.
즉 완전 탐색은 불가능!
투 포인터?
합을 0으로 만들어야 한다고 하니, 이전에 풀었던 용액 문제가 생각이 난다.
그 때는 두 용액을 합쳐서 0에 가장 가까운 경우를 출력했었다.
하지만 이번에는 세 학생을 합쳐 0으로 만들어야 한다.
투 포인터만으로는 풀 수 없을 것 같고, 아이디어가 필요해 보인다.
우선 학생들의 합을 맞추기 용이하도록 오름차순으로 정렬을 해놓자.
투 포인터 + 브루트 포스
투 포인터와 브루트 포스를 한 번 결합해보는 건 어떨까?
두 번째 학생부터 마지막 학생의 앞 학생까지 투 포인터를 적용하는 것이다.
그럼 학생을 훑는 시간 복잡도 O(N)이 걸릴 것이고,
투 포인터 알고리즘의 시간 복잡도 O(N)이 걸리니, 결국 O(N^2)이 된다.
10000명의 학생이 와도 100,000,000 정도이니 시간 초과는 괜찮을 것이다.
void two_pointer(int target) {
int front_ptr = 0, rear_ptr = num - 1;
while (front_ptr < target && rear_ptr > target) {
int sum = teammates[front_ptr] + teammates[target] + teammates[rear_ptr];
if (sum < 0)
front_ptr++;
else if (sum > 0)
rear_ptr--;
else if (sum == 0) {
front_ptr++;
answer++;
}
}
}처음엔 함수를 위와 같이 구현했다.
하지만 합이 0이 되었을 때, 어느 쪽 포인터를 줄일 지가 문제였다.
중복되는 케이스의 조합이 나올 때, 그걸 탐지할 수가 없는 것이다.
해당 부분만 해결하면 해결될 것 같은데 고민을 한 번 해보자..
이분 탐색 + 브루트 포스
결국 고민 끝에 다른 사람의 풀이를 참고했다.
나처럼 투 포인터로 해결하는 방식은 거의 불가능해 보였다.
가장 간단한 방식은 이분 탐색과 함께 브루트 포스를 이용하는 것 이었다.
2개의 수를 고정시켜놓고, 나머지 하나의 수를 이분 탐색으로 찾는 것이다.
그럼 O(N * N * logN)의 시간복잡도가 소요되므로, 시간적으로도 괜찮다.
최종적으로 아래와 같이 구현되었다.
sort(teammates, teammates + num);
// 우선 포인터를 사용하기 위해 정렬이 필요하다.
for (int i = 0; i < num - 1; i++) {
for (int j = i + 1; j < num; j++) {
ll sum = teammates[i] + teammates[j];
int front_ptr = lower_bound(teammates + j + 1, teammates + num, -sum) - teammates;
int rear_ptr = upper_bound(teammates + j + 1, teammates + num, -sum) - teammates;
answer += (rear_ptr - front_ptr);
}
}기본적으로 lower_bound, upper_bound는 이분 탐색으로 동작한다.
꽤 많이 사용되는 것 같으니 제대로 익혀두자..