안녕하세요. Ruk 입니다.
3sum 문제는 지금까지 풀어보았던 Medium 난이도중에서 가장 어렵게 느껴졌습니다.
문제를 어떻게 풀었는지 좀 더 자세히 풀이를 하도록 노력해볼게요. ^^
참고로 저의 풀이 과정을 보면
정말 많이 풀고 실패하기도 하며 수정하기도 하고 속도와 메모리까지 개선하느라 애먹은 문제였습니다.
예전에 풀어봤어도 다시 풀어보고 해도 아직도 어렵내요.
최근에 제가 푼 코드를 보고 풀이를 해볼게요.
입력 nums의 길이가 3보다 작다면 반환이 불가능 하기에 예외처리를 합니다.
a, b, c의 합이 0을 만들어야 하므로 nums를 정렬하여 작은수부터 체크해나가려고 합니다.
즉 a는 음수 c는 양수가 되고 a+b+c가 0이 되는 경우를 중복 없이 찾아갈 것 입니다.
조건을 조금 정리하면
a 는 음수여야 한다.
a 는 같은수가 2번 올 필요가 없다. 이유는 a로 0이 되는 케이스를 이미 찾았기 때문.
b, c가 같은 수가 올 수도 있다.(ex : -2, 1, 1) 즉 중복되는 숫자가 2개 이상인지 체크되어야 한다.
위 조건을 구현한 코드가 되겠습니다.
정렬하여 작은수부터 for문을 돌리고, a위치에 이전 값과 중복되면 패스, 음수가 아니여도 패스.
0이되는 값이 있는지 체크하여 result에 저장.
조건만 잘 설정하면 풀 수 있는 문제였지만, 속도와 메모리를 최적화하기까지 저는 좀 걸렸내요.
익숙해지지 않으면 코딩테스트에 유사 문제가 출시 되었을 때 시간내에 최적의 알고리즘을 짜기 힘들것 같다고 느끼며 반성하게 되는 문제였습니다.