2 Pointer - 값들을 합해서 원하는 값이 되는 숫자들의 모음을 아는 방법

코딩테스트에서 3-Sum 문제유형이 나왔다.

처음 문제를 풀 때는 for 문을 마구 돌리며 i, j, k 를 다 돌며 합해서 0이 되는 값을 배열에 push해주는 경우를 생각했다. 

 

하지만 집에 와서 다시 풀어보니 같은 숫자 ex) [[-1, 0, 1], [2, 0, -2], [-1, 0, 1]] 이렇게 같은 배열이 중복되는 경우와 0으로만 이루어진 배열에서도 따로 예외처리를 해줘야하는 등 더 복잡하고 for문을 많이 중첩해서 쓰니 O(n^3)의 시간복잡도가 나오는 방법이다.

 

풀면서도 이건 아니다싶었지만 생각이안나 일단 이 잘못된 방법으로 다시 풀어보았다. 

 

 

(안좋은 방법)

 어찌저찌해서 test case는 다 통과되었지만 submit했을 때 55 / 312 testcases passed가 떴다. 

test case

[-1,0,1,2,-1,-4]

[0,1,1]

[0,0,0]

 

이 방법을 풀기위해 pointer를 사용하는 방법이 있었지만 정확히는 모르고있어서 Pointer 개념을 적용해서 다시 풀었더니 훨씬 간편하고, 연속으로 중복되는 숫자가 나와도 예외처리가 단순했기에 훨씬 깔끔하고 쉽게 풀렸다. 

 

i, j, k를 쓰는 것도 좋지만 pointer개념을 이해하기위해 left, mid, right 변수를 사용했다. 

 

첫 번째 방법으로는 for문의 중첩으로 시간복잡도가 O(n^3) 이었다면2pointer를 이용한 후 시간복잡도는 O(nlogn)으로 향상되었다. 

 

 

--(참고)