같은 길이의 수열 4개가 주어졌을 때, 각 배열에서 수를 하나씩 뽑아서 합이 0이 되는 경우의 수를 구하는 문제입니다. 먼저 시간복잡도를 예상해보자면, 단순 탐색은 $O(n^4)$, C와 D를 하나로 합친 후 정렬하여 두 포인터 기법을 적용하는 것은 $O(n^3)$입니다. 그런데 n3도 힘들어보이는 제한 시간입니다. $O(n^2\log n)$이 필요해보입니다.
먼저 주어진 배열을 적당히 조작하여 시간 복잡도를 줄이는 방법을 생각해보아야겠습니다. 일단 배열을 2개씩 합쳐보죠. 두 배열을 골라 각 합을 하나의 배열에 저장하고, 나머지 배열 2개의 합을 또 다른 배열에 저장하여 $n$짜리 배열 4개를 $n^2$짜리 배열 2개로 바꿉니다. 이제 결과로 나온 배열 2개를 정렬합니다. 이 때 $O(n^2\log n)$입니다. 그 뒤, 한 배열은 앞부터, 나머지 한 배열은 뒤부터 두 포인터 기법을 사용하여 합이 0인 경우를 찾습니다. 조작의 결과로 나온 배열에 중복인 원소가 존재할 수 있다는 점에 유의하여 경우의 수를 구하고 이를 출력하면 됩니다.
배열 합치는 과정 $O(n^2)$, 정렬하는 과정 $O(n^2\log n)$, 그리고 두 포인터 기법을 사용하는 과정 $O(n^2)$을 모두 합치면 $O(n^2\log n)$이 나옵니다.
소스 코드
| 언어 | 코드 | 시간 | 비고 |
|---|---|---|---|
| C++ | 코드(Github) / 코드(백준) | 2021-03-10 23:02:28 |