[백준] 7453번: 합이 0인 네 정수

https://www.acmicpc.net/problem/7453

7453번: 합이 0인 네 정수

당연한거지만 모든 순서쌍 조합을 for문으로 만들려고 하면 시간복잡도가 O(n^4)가 되기 때문에 최대 4000 ^ 4번 연산을 해야하므로 시간 초과가 발생할 것이 뻔하다...

두 포인터 알고리즘을 사용하면 O(n^2)으로 줄일 수 있따.

 

풀이) 

A, B, C, D 리스트를 입력받는다.

 

가능한 A[a], B[b]의 합을 모두 구해 AB 리스트에 저장하고, AB 리스트를 정렬한다.

CD 리스트도 같은 방법으로 만든다.

 

두 포인터 알고리즘을 이용해서 모든 순서쌍을 구한다.

AB 리스트는 가장 왼쪽부터, CD 리스트는 가장 오른쪽부터 탐색을 시작한다.

 

AB 리스트의 원소와 CD 리스트의 합이

i) 0보다 크면 합이 작아져야 하므로 CD 리스트의 포인터를 왼쪽으로 옮긴다.

ii) 0과 같으면 AB 리스트에서 중복된 원소의 개수 * CD 리스트에서 중복된 원소의 개수를 cnt에 더한다.

각각 중복된 원소의 개수만큼 포인터를 옮긴다.

iii) 0보다 작으면 합이 커져야 하므로 AB 리스트의 포인터를 오른쪽으로 옮긴다.