Two-Sum 문제

풀 수 있는 방법이 좀 다양한데, HashTable(set)의 기억을 잘 활용하는 문제기도 하고, Remainder의 특이한 케이스가 인상깊었던 문제여서 정리해둔다. 단골인 편인지 어김없이 GeeksforGeeks 에도 실려있다.

문제는 대충 다음과 같다. (GeeksforGeeks에서 그대로 퍼왔습니다)

Input: arr[] = {0, -1, 2, -3, 1}
        x= -2
Output: Pair with a given sum -2 is (-3, 1)
              Valid pair exists
Explanation:  If we calculate the sum of the output,1 + (-3) = -2

Input: arr[] = {1, -2, 1, 0, 5}
       x = 0
Output: No valid pair exists for 0

그러니까, 리스트에서 2개의 숫자를 더해 목표하는 값을 만드는 방법을 찾으라 이 말이다.

Naive solution은 역시나… 전통의 2중루프이다!! O(n^2) 되시겠습니다. 사실상 써먹을 수 없는 알고리즘 취급…

또 생각해 볼 수 있는 방법은 Sort+TwoPointer*(l, r 쓰는거)* 이다. pseudocode는 대충…

1. Sorting 한다.
2. l=0, r=len(n)-1 으로 초기값
3. val gt(>) arr[l]+arr[r] 이면 l++, val less면 면 r--; val eq면 정답!

이 경우 loop 도는 건 O(n) 으로 끝나지만 정작 Sort complexity가 제일 크다. 따라서 O(nlogn)

해시로 풀 수도 있다. for loop을 한번 돌리는데, 돌면서 Hash[sum-A[i]] 에 해당하는 값이 있는지 찾아본다. 없으면 Hash[A[i]] 를 저장한다.

Hash는 A[0] ~ A[i-1] 까지의 값을 담고 있는 상황이 될 것이고, 따라서 저건 Hash 테이블에 “A[0]~A[i-1] 중에서, A[i]와 합쳤을 때 sum 이 되는 원소를 본 적이 있니?” 라고 질문하는 것과 똑같다.

즉, Hash 테이블이 일종의 기억 역할을 해주는 것이다. Memory 때문에 Optimal 정답은 아니라도, 꽤 참신한 풀이 방법이라 기억해 둘 가치는 있음.

루프 1번에 모든 게 끝나므로 의외로 이 방식도 O(n).

Remainder

여기서의 꽃(?)은 Remainder을 쓰는 방법이다. 여기에서는 두 가지의 전제가 필요한데…

1. answer(two numbers) 은 반드시 sum 보다 작을 것이다
2. 그러니까, answer % sum == answer 임을 보장할 수 있다

그래서 아래와 같이 대충 알고리즘을 짤 수 있다.

1. int x[sum] 준비
2. list를 돌면서, list[i] < sum 이면, x[i] = list[i] % sum 으로 채운다.
3. 이제 x를 보고 정답이 존재하는지 확인하면 됨! (len(x) 만큼의 for loop 한번)

이걸 또 최적화하면, x를 따로 안 만들고 Hash에 바로바로 꽃아넣어서 체크하도록 할 수 있다. 이 겨우 시간복잡도가 O(n) 이 된다. 뭐 별 차이는 없네

Sabun: Sum of triplet

세 수의 합은 어떻게 구할 수 있을까? 이것도 GeeksforGeeks에 있다.

간단히 요점만 정리하면, Sort+TwoPointer 방식을 변형했다. 그러니까,

1. Sort를 한다.
2. for (i = 0; i < n; ++i) 루프를 돌리고
3. for (j = i+1; j < n; ++j) 루프를 돌리는데
4. 여기서 l=j, r=n-1 로 해서 TwoPointer 방식으로 수행.

이 경우 O(n^2) .

또다른 방법

Hash를 써서, 앞서 봤던 값들을 기록해 두는 방식으로 푸는 방법도 있다. 이 경우 위처럼 for loop를 두개 돌려야 하고, Hash[sum - A[i] - A[j]] 가 존재하는지, 존재하지 않는다면 Hash[A[j]] 를 기록해두는 방식이다. 즉 Hash가 세번째 값에 해당하는 후보를 담고있는 셈.

for loop 2중이니 동일하게 O(n^2) 이다. 근데 메모리 복잡도가 twoPointer만 못하니 딱히 쓸 이유는 없고, 이렇게 풀수 있구나 정도 …

… 근데 너 왜 Easy냐? 구현 자체는 쉬워서 근가 -_-;