[LeetCode] 15. 3Sum (C++)

문제

 

https://leetcode.com/problems/3sum/

3Sum - LeetCode

 

풀이

 

난이도: Medium 

 

Two Sum문제를 조금 더 발전시킨 문제.

 

문제 해결의 핵심은 세 개의 값을 더해 0(x + y + z = 0)을 만드는 것보다 

y + z = -x 로 두 값을 더해 특정 값을 만드는 것으로 문제를 변형하는 것이다.

따라서 모든 원소 값을 x로 한 번씩 설정하여 스위핑으로 서치를 하면 O(n*n)의 시간 복잡도로 해결할 수 있다.

 

단, x를 정하고 y와 z값을 찾을 때 y와 z값은 항상 x의 오른쪽에서 찾아야 한다는 제한을 두어야 한다.

제한을 두지 않으면 다음과 같이 중복된 값들이 3번 찾아지게 된다.

 

 

하지만 더한 값이 -x가 되는 두 값을 x의 오른쪽 범위에서만 찾는다면 중복된 불필요한 연산을 줄일 수 있다.

 

 

이제 스위핑으로 두 값만 찾아 내고 싶지만 이번 문제는 Two Sum과는 달리 중복되는 원소가 존재할 수 있다.

정답으로는 동일한 세가지 원소를 갖는 배열은 하나만 존재해야 하므로 동일한 원소들이 x로 선택되지 않도록 지나가 주자.

또한 동일한 원소가 여러 개 있다면, 이미 y와 z로 선정된 원소가 다시 y와 z로 선택될 수도 있으므로 다음 원소 값이 선택될 수 있도록 지나가 주자.

 

 

 

 

코드