출처
Koreatech OnlineJudge(링크)
문제이해
수열에서 수를 3개 뽑아서 합이 0이 되는 경우의 수를 구한다. 중복되는 경우는 계산하지 않는다.
문제접근
단순히 3중 for문으로 반복하여 찾으면 시간복잡도는 O(n^3)으로, 시간초과가 나서 통과하지 못한다.
세 수 i, j, k가 있을 때 i를 처음부터 한 칸씩 증가시키면서 각 i에 대해 j와 k를 찾으면 빠른데,
이 방법을 사용하려면 먼저 수열을 정렬해야 한다.
i+j+k > 0이면
k를 감소시키고,
i+j+k < 0이면,
j를 증가시킨다.
i+j+k = 0이면,
경우의 수를 한 번 카운트하고, k를 감소시키고 j를 증가시킨다.
그리고 반복문의 종료조건은 j와 k가 서로 교차했을 때이므로 아래 그림과 같은 경우까지 반복하게 된다.
시간복잡도는 O(n^2)이다.
이 부분을 코드로 보면 아래와 같다.
prv 변수는 중복되는 순서쌍을 제외하기위해 만든 변수이다.
(전체 코드는 맨 아래에 있음.)
while(j<k) { if(arr[i]+arr[j]+arr[k] > 0) --k; else if(arr[i]+arr[j]+arr[k] < 0) ++j; else { if(prv != arr[j]) { ++cnt; prv = arr[j]; } --k; ++j; } } |
구현
수열을 정렬할 때 std::sort()를 사용하면 간단하다.
위에서 중복을 제거하는 부분이 있었는데, 바깥쪽 반복문에서 i, j, k 중 i가 중복되는 경우 또한 제거한다.
실행결과
코드
https://github.com/tibyte/algorithm-problems/blob/master/koreatech/1005/1005.cpp