LeetCode 15. 3Sum
문제분석
숫자로 이루어진 배열이 주어 질 때, 합이 0이 되는 세개의 원소를 가지는 유니크한 집합을 리턴하기
인풋: [-1, 0, 1, 2, -1, -4]
아웃풋: [
[-1, 0, 1],
[-1, -1, 2]
]
이 때 주의할 점은 [-1, 0, 1] 과 [0, 1, -1] 은 같은 집합이기 때문에 최종 결과값에 담기면 안된다.시행착오
처음엔 가능한 조합을(nC3) 모두 구해서 합이 0이 되는 조건으로 조합을 필터링 한 후에, unique 한 세개의 원소로 이루어진 집합을 리턴하기 위해서 다시 모든 결과 값에 대해서 string으로 변환하고 Set 자료구조에 담아서 중복되는지 안되는지를 검사했다.
원하는 결과값들을 얻을 순 있었지만 최종 테스트 케이스에서 Time Limit Exceeded(시간 초과)로 통과하지 못한 코드다.
시행착오 코드
돌파구
앞선 포스팅에서 twoSum의 풀이를 다루었다.
세개를 더하는 것은 사실 앞에 하나의 값을 고정 뒤에 올 두개의 합을 구하면 된다. 즉, 고정값 + twoSum 알고리즘을 통해 리턴된 값을 더해서 0이 되도록 하면 된다.
[-1, 0, 1, 2, -1, -4]
1. -1 고정, twoSum( [0, 1, 2, -1, -4], targetNumber: 0 - (-1) ) 을 보내준다.
2. targetNumber가 0 - (-1) = 1 을 만족하는 배열이 리턴된다.
3. [[0, 1], [2, -1]] 이 배열에 대해서 고정된 값을 insert 해준다.
4. [ [-1, 0, 1], [-1, 2, -1]] 리턴.그리고, 중복을 피하기 위해서 3가지 장치를 걸었다.
- 주어진 배열을 순회하기 전에 sort() 함수로 배열을 정렬하기
- 한 번 fixed 되어서 검사한 값은 후에 다시 검사하지 않도록 Set 자료구조를 사용해서 이미 고정되었으면 다시 남은 배열에 대해서 twoSum 을 구하지 않도록 한다.
- twoSum 함수 내에서도 Set 자료구조를 사용해서 같은 쌍이 리턴되지 않도록 한다.
