[LeetCode] 1. Two Sum (C++)

문제

 

https://leetcode.com/problems/two-sum/

Two Sum - LeetCode

 

풀이

 

난이도: Easy

 

브루트 포스로도 간단히 해결 가능한 문제이지만

정렬 후 스위핑 알고리즘을 적용하여 훨씬 빠르게 해결 가능한 문제이다.

 

주어진 배열을 오름차순으로 정렬하고 가장 왼쪽끝(left)은 가장 작은 수이고 가장 오른쪽 끝(right)은 가장 큰 수 일 것이다. 이 두 수를 합한 수 add_num라고 할때, 두 가지 경우를 생각해보자.

 

1. add_num > target

이 두 수(left수와 right수)를 합한 수(add_num)가 만약 target보다 작다면 --right를 한다.

배열은 오름차순으로 정렬되어 있으므로 right 수를 왼쪽으로 한 칸 옮긴 수는 항상 이전의 right 수 보다 작다.

따라서 add_num은 작아져 target에 가까워진다.

 

2. add_num < target

이 두 수를 합한 수(add_num)가 target보다 크다면 ++left를 한다.

left 수를 오른쪽으로 한칸 옮긴 수는 항상 이전의 left 수 보다 크다.

따라서 add_num은 커진져 target에 가까워진다.

 

따라서 이를 반복하다보면 정답인 A와 B에 각각 left와 right가 도달하게 된다.

하지만 이때 left와 right가 A와 B를 지나칠 수 있지 않을까 생각할 수 있다.

다음과 같이 right가 B를 지나갔다고 생각해보자.

 

 

right가 B를 지나가기 위해서는 1번 경우(add_num > target)인 두 수의 합이 target보다 큰 경우이다.

지금 right가 B에 도달했다고 가정해보자.

이때 1번을 만족하기 위해서는 target이 add_num보다 작아야 한다.

하지만 left는 A보다 항상 작기 때문에 다음이 성립한다.

 

 left_num < A

 left_num + B < A + B (= target) 

 

따라서 right가 B에 도달했다면 right는 B를 지나지 않고 계속 유지될 수밖에 없다.

반대의 경우에도 이가 성립하므로 A와 B를 항상 찾을 수 있다.

 

 

 

 

코드