출처

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




+ Recent posts