백준 2473: 세 용액 (Swift)

투포인터의 시간복잡도는 어떻게 될까.

생각해보니 투포인터의 시간복잡도에 대해서 크게 생각해본 적이 없는 것 같았다.

 

이 문제를 처음 접하고 완전탐색으로 풀이했고, 당연히 시간초과가 떴다.

 

투포인터는 주어진 배열이 정렬되어있을 때, 정렬되지 않았을 때 모두 사용하는 경우가 있다.

여기서는 시간복잡도를 최소화하기 위해,그리고 문제 특성상 두 포인터를 양 끝에 두고 가운데로 좁혀들어와야한다.

 

예를 들어 -99 -97 -50 -15 14 51 103 과 같이 배열이 주어져있고, 합이 0에 가까워지는 쌍을 찾는다고 생각해보자.

이때 0,1번 인덱스에 start,와  end 포인터를 두고 탐색한다면, 우리는 end가 103에 도착해 (-99, 103)쌍을 처음이자 마지막으로 얻게 될 것이다.

하지만 양 끝에서 출발할 경우, (-50, 51), (-15, 14)를 모두 찾아낼 수 있다.

 

1차원 배열에서 두개의 포인터로 완전탐색을 한다면, 시간복잡도는 nC2 = (n-1)*(n-2) / 2 로 O(n^2)이 될 것이다.

하지만 투포인터로 탐색한다면, 최악의 경우에도 (n-1) + (n-2) 하여 O(n)의 시간복잡도를 가지게 된다.

 

이 문제는 세개의 포인터로 완전탐색하여 O(n^3)의 시간복잡도로 풀이하면 안되고,

하나의 포인터는 고정해가며(n), 나머지 배열 범위에서 두개의 포인터로 투포인터를 수행해야한다(O(n))

이렇게 하려면 배열이 정렬되어 있어야하므로 O(nlogn)의 시간복잡도로 오름차순 정렬을 먼저 수행해야한다.

 

이렇게 하면 시간초과 없이 문제를 해결할 수 있다.