2473번 - 세 용액(python3)

문제 링크: www.acmicpc.net/problem/2473

2473번: 세 용액

정말 오랜만에 문제를 풀고 글을 쓰네요. 이번 문제는 투 포인터를 써서 해결하는 문제입니다. 브루트 포스를 써서 해결할 수도 있지만 그럼 시간 복잡도가 $O(n^{3})$까지 올라가서 시간 초과가 뜰 겁니다. 투 포인터를 사용하면 $O(nlogn + n^{2}) = O(n^{2})$에 해결할 수 있습니다.

 

문제는 간단하게, n개의 숫자가 주어져 있을 때 합이 0에 가장 가까운 세 수를 찾는 것입니다. 문제에서 주어진 예시는 n=5, [-2, 6, -97, -6, 98]인데, 이 경우 -2, -97, 98을 더해 -1을 만드는 것이 정답입니다. 만약 답이 여러 개일 경우 한 가지 케이스만 출력하면 됩니다.

 

다음은 문제 풀이에 사용한 코드입니다.

우선 투 포인터 사용을 위해 정렬을 해 주고, 기준이 되는 res값을 임의의 최댓값으로 잡아줍니다. 이제 투 포인터로 문제를 풀어봅시다.

 

투 포인터는 array의 양 쪽 끝에 포인터를 두고, 문제 조건에 맞게 적당히 왼쪽 또는 오른쪽 포인터를 가운데 방향으로 움직이면서 정답을 찾는 과정입니다. 여기서는 합이 0에 가장 가까운 세 숫자를 찾는 것이 목적이므로, 값 하나를 고정시켜두고 나머지 두 값을 투 포인터로 찾습니다.

 

n=9인 상태에서 투 포인터 첫 적용 시 상태

정렬이 이미 된 상태이므로 우선 전체에서 가장 작은 값(검정)을 고정시키고, 그 다음 숫자(빨강)를 left pointer가, 전체에서 가장 큰 값(초록)을 right pointer가 가리키도록 합시다. 이 때 고정된 숫자(lst[i])와 포인터가 가리키는 두 숫자((lst[l_p], (lst[r_p]))의 합의 절댓값이 res의 절댓값보다 작으면 현재 시점에서 정답을 sol_candi = [lst[i], lst[l_p], lst[r_p]]로 업데이트 하고, res값 또한 고정된 숫자와 포인터가 가리키는 두 숫자의 합(cur_sum = lst[i]+lst[l_p]+lst[r_p])으로 업데이트합니다.

 

이제 포인터를 움직일 시간입니다! 포인터를 움직이는 건 cur_sum값에 따라 결정됩니다. 숫자가 담긴 lst 내 값들은 모두 정렬되어있음을 기억합시다.

1. cur_sum < 0인 경우
  - cur_sum이 더 커져야 0에 가까워지기 때문에 왼쪽 포인터를 오른쪽으로 움직여 다음 cur_sum값이 커지도록 합니다.

2. cur_sum > 0인 경우
  - cur_sum이 작아져야 0에 가까워지기 때문에 오른쪽 포인터를 왼쪽으로 움직여 다음 cur_sum값이 작아지도록 합니다.

3. cur_sum = 0인 경우
  - 정답입니다! 현재 저장되어있는 sol_candi 내 값들을 오름차순으로 출력하고 종료합니다.

투 포인터를 적용하는데 $O(n)$이 걸리고, 고정되는 원소 또한 최대 n개이기 때문에 시간 복잡도는 $O(n^{2})$입니다. 정렬에 $O(nlogn)$이 걸리긴 하지만 $O(n^{2})$가 더 크니 이게 전체 시간복잡도라고 생각하면 됩니다.

 

solved.ac 기준 Class 5의 essential 문제입니다만 투 포인터를 어떻게 적용시켜야 할 지 파악만 되면 쉽게 풀 수 있는 문제입니다. 친구랑 1주일에 백준 몇 문제를 푸는 스터디를 시작했는데, 풀면서 인상깊은 문제는 가능한 글로 정리할 수 있도록 하겠습니다....

 

여담으로, 이 문제를 풀었다면 조금 더 쉬운 문제인 2467번 용액 문제를 날먹할 수 있습니다... 원래는 2467번 문제를 먼저 풀고 이 문제를 풀어야 하는 것 같은데 저는 반대로 풀었네요.