[Algorithm] 투 포인터 (feat. leetcode Two Sum, Three Sum) | LIM

📚투 포인터 알고리즘이란

투 포인터 알고리즘은 리스트에 순차적으로 접근해야 할 때 2개의 점의 위치를 기록하면서 처리하는 알고리즘을 의미한다. 

예를 들어서 2, 3, 4, 5, 6, 7번 학생을 가리켜야 할 때 우리는 '2번부터 7번까지의 학생'이라고 부르곤 한다. 

이처럼 리스트에 담긴 데이터에 순차적으로 접근해야 할 때는 '시작점' 과 '끝 점' 2개의 점으로 접근할 데이터의 범위를 표현할 수 있다.

 

그냥 naive 방식인 반복문을 쓰다보면 시간 초과가 걸리는 경우에 투 포인터를 사용하면 메모리와 시간 효율성을 높일 수 있다. 

포인터는 크게 두 가지 방식으로 쓰인다. 

 

1. 앞에서 시작하는 포인터와 끝에서 시작하는 포인터가 만나는 형식 또는 원하는 값 target을 찾을 때까지

2. 또는 빠른 포인터(fast runner) 가 느린 포인터(slow runner) 보다 앞서는 형식

 

위 두가지 방식을 예제를 통해 살펴보자.

 

✔️ 형식1: 예제 - LeetCode [Two Sum II - Input Array Is Sorted]

문제: https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/

Two Sum II - Input Array Is Sorted - LeetCode

 

이 문제는 '특정한 합을 가지는 두 개의 원소 찾기' 문제이다.

 

문제를 푸는 방법은 다음과 같다. 

1. 시작점(i 포인트)과 끝점(j 포인트) 이 각각 첫 번째 인덱스와 마지막 인덱스를 가리키게 한다.

2. 두 수의 합이 target 보다 작으면 i 포인터를 뒤로 하나 이동 (i += 1)

3. 두 수의 합이 target 보다 크면 j 포인터를 앞으로 하나 이동 (j -= 1)

 

풀이는 다음과 같다. 

 

 

 

✔️ 형식2: 예제 - LeetCode [Remove Duplicates from Sorted Array]

문제: https://leetcode.com/problems/remove-duplicates-from-sorted-array/

Remove Duplicates from Sorted Array - LeetCode

이 문제는 '두 포인터가 앞에서 시작하는데 속도가 다르게 움직이는 형식'이다. 일명 토끼와 거북이 형식이다.

 

이 문제를 푸는 방법은 다음과 같다. 

1. slow와 fast는 각각 인덱스 0과 1에서 시작한다.

2. fast 가 1부터 시작해서 움직이면서 slow 와 숫자가 달라지면 slow가 앞으로 이동하면서 그 숫자를 fast 포인터가 가리키는 숫자로 바꿔준다.

3. 이러한 loop 를 반복하다 보면 배열이 nums=[0,0,1,1,1,2,2,3,3,4]에서 nums=[0,1,2,3,4,2,2,3,3,4]로 바뀌고

slow +1 이 중복된 숫자가 없는 길이이기 때문에 slicing 해서 return 하면 된다. 

 

다른 블로그에서 아래 그림보고 한 번에 이해했다. 출처는 그림 밑에 남겨두었다.

https://benn.tistory.com/9

 

풀이는 다음과 같다. 

 

 

✔️ 응용 예제 - LeetCode[3 Sum]

문제: https://leetcode.com/problems/3sum/description/

3Sum - LeetCode

 

이 문제는 [Two Sum II - Input Array Is Sorted] 여기에서 3 Sum 으로 확장된 문제이다.

 

이 문제는 다음과 같이 풀었다.

1. 이 문제는 먼저 nums 가 정렬되어 있지 않으므로 정렬을 먼저 해준다. 

2. 투 포인터를 이용해서 현재 값에서 왼쪽, 오른쪽 값을 정해준다. 

3. 왼쪽 + 현재 값 + 오른쪽 값 더해서 0 보다 크면 오른쪽 인덱스를 1 감소시키고, 작으면 왼쪽 인덱스를 1 증가시킨다.

4. 합해서 0이 되면 [왼쪽, 현재값, 오른쪽 값]을 반환 리스트에 추가한다.

 

풀이는 다음과 같다.

 

 

통과는 했지만 생각보다 Runtime 이 너무 오래 걸렸다. 

다른 방법을 찾아보니 파이썬 알고리즘 코딩 인터뷰 에 나온 풀이 방식은 다음과 같았다. 

천천히 다시 이해해 봐야겠다.