Leetcode 15번 문제 풀이

개요

Leetcode 에서 알고리즘 문제를 풀고 배운 내용을 정리하기 위해 작성하였습니다.

 

문제 : 15. 3Sum

주어진 배열에서 요소 3개를 골라 합했을 때 0이 되는 것들만 배열로 추려내서 반환하기. 단 중복되는 것은 피하기(not allowed duplicate triplets)

 

풀이

문제 풀이를 위해서 먼저 주어진 배열을 오름차순으로 정렬해야 한다. 정렬을 하면 합했을 때 0이 되는 요소를 찾기 쉬워지기 때문이다.

 

그래서 만약 다음과 같이 정렬을 했다고 하자.

 

현재 배열 요소가 -2 라면, 그 다음 요소와 배열 마지막 요소로부터 인덱스를 줄여나가면서 적합한 요소를 추려낸다. 이 때 현재 배열 요소의 다음 값 인덱스를 low, 배열 마지막 요소 인덱스를 high 라고 하자.

 

현재 배열 요소가 -2 일때 합이 0이 되려면 2를 더해야 한다. 그러므로  -2 와 4 또는 0 과 2가 필요하다.

만약 low와 high 사이 구간에 있는 요소들의 합이 구하고자 하는 값보다 작다면, 이는 low 인덱스가 너무 좌측에 있어 값이 작게 나오는 것이므로 low값을 증가시켜준다.

만약 요소들의 합이 구하고자 하는 값보다 크다면, 이는 high 인덱스가 너무 우측에 있어 값이 크게 나오는 것이므로 high값을 감소시켜준다.

만약 요소들을 합했을 때 원하는 값이 되면 이를 정답 배열에 현재 배열 요소를 포함해 배열 형태로 넣어준다. 현재 경우 -2 와 4가 최초로 원하는 값이 되므로 이를 배열에 넣어준다.

 

그래서 범위는 다음과 같이 좁혀지게 된다.

 

이어서 정답이 되는 요소들을 찾기 위해 인덱스 범위를 좁혀나간다. 이 때 low 위치의 값과 이후값이 같다면 low를 증가시켜주고 high 위치의 값과 이전값이 같으면 high를 감소시켜준다. 왜냐면 해당 경우에 대한 값을 이미 찾았기 때문이다. 문제는 중복을 허용하지 않기 때문에 같은 경우에 대한 값을 또 찾을 필요가 없다. 예를 들어, 위 경우 low 인덱스에 위치한 값은 -2 이고, 현재 배열 요소 -2 와 합하면 -4가 되며 모두 합하여 0이 되게하는 값은 4이다. 하지만 -2와 4는 우리가 앞서 이미 찾은 것이므로 정답 배열에 또 넣을 필요가 없다, 그러므로 값이 같으면 low와 high 인덱스 값을 증감시켜주어 스킵하게 한다. 만약 원하는 값을 또 찾으면 이를 정답 배열에 넣어준다.

 

이런 식으로 중복을 피해 배열 내 값을 모두 찾아주면 된다.

 

코드

 

코드로 봤을 때 좀 더 이해가 필요한 부분이 있으므로 더 살펴보도록 한다. 앞서 얘기한 것처럼 배열을 정렬하고 이에 대해서 loop를 돌며 검사를 한다. 이 때 for loop는 배열 길이 - 2 만큼 반복을 한다. 왜냐면 인덱스 범위를 벗어나지 않게끔 검사를 하기 위해서이다. 우리는 low, high 인덱스를 이용하여 검사를 하고 이들은 현재 배열 요소 인덱스 보다 큰 값을 가진다. 그러므로 이들을 위한 값을 제외시켜 준것이 -2 이다. 그림으로 살펴보자

 

 

위 그림과 같이 1이 배열 마지막 요소라고 하자. 현재 배열 요소가 -1 이라고 했을 때 전체 루프를 돌며 검사를 하면 배열의 범위를 벗어나서 검사를 하므로 인덱스 오류가 발생한다. 루프가 전체보다 -2 만큼 이전에 종료되야 low와 high 값을 잘 설정해주게 되고 코드가 정상적으로 동작을 하기 때문에 이 같이 해준다.

 

또 현재 배열 요소 값이 이전의 값과 똑같다면 스킵을 해준다.

 

배열의 두번 째 요소인 -2에 대해서 검사를 하여 정답을 구했고 이제 그 다음 요소에 대해서 검사를 한다고 하자.

하지만 현재 값이 이전 값과 똑같다면 중복된 값을 구하는 것이므로 구할 필요가 없다. 그러므로 서로 다른 값이 될 때 검사를 하도록 한다. 위 경우 현재 값이 0이 되면 다시 검사를 하게 된다.

 

추가적으로 코드 내에서 while 루프 내 while 루프에서 low, high 인덱스를 각각 증감시켜 준뒤 또 한번 low, high 값을 증감시켜주는데, 이는 값을 제대로 찾아주기 위해서이다. 이에 대해서 의아해할 수 있으므로 다음을 보자.

 

low의 경우 조건문에서 low 인덱스 요소와 low+1 인덱스 요소를 비교하여 같으면 low를 증가시킨다. 그림 예를 통해서 보면 현재 : -2 , 다음 : -2 일 때 low를 증가시키고 이제 각각 -2, 0 이 된다. 이제는 서로가 다르므로 조건문을 넘어가는데 이 때 low를 증가시켜줘야 현재 low 인덱스 요소가 0이 되면서 제대로 검사를 할 수 있게 된다. high 를 감소시키는 것도 같은 이유이다.

 

 

출처

https://www.youtube.com/watch?v=qJSPYnS35SE&t=477s