해법 1 - O(k²) 시간 (분할정복)

k개 카드에 대해 주어진 크기 관계를 방향성 그래프로 치환하여 생각할 수 있다. 크기를 최소 혹은 최대로 결정하기 위해서 가장 앞에 오는 카드의 숫자를 우선적으로 결정하여야 하므로 가장 앞에 오는 카드를 기준으로 잡고, 그래프 탐색을 통하여

1) 그 카드보다 큰 카드들의 집합

2) 그 카드보다 작은 카드들의 집합

을 구한다. 이는 그래프 원소 개수에 비례하는 시간복잡도로 취할 수 있으며 집합을 구한 후에 기준이 되는 카드의 숫자는

1) 최대값을 구할 경우, 큰 카드들의 집합에서 사용하는 숫자들의 최소값 -1

2) 최소값을 구할 경우, 작은 카드들의 집합에서 사용하는 숫자들의 최대값 +1

으로 결정된다. 기준을 사이에 두고 분리된 두 그래프에 대해서도 재귀적으로 똑같은 시행을 하여 모든 카드의 숫자를 채워나갈 수 있다. 한 시행을 통해 그래프가 두 부분으로 분리되므로 이 알고리즘은 가장 좋은 경우 수행시간이 O(k log k), 최악의 경우 수행시간이 O(k²)이다.

해법 2 - O(P+k log k) 시간 (위상정렬)

위 분할 정복 해법의 최적화된 구현이라고 할 수 있다. 예를 들어, 최소값을 구하는 경우에는 1) 먼저 크기관계 그래프를 큰 카드에서 작은 카드로 방향성을 주어 구성한 후 2) indegree가 0인 노드인 카드들 중 가장 자릿수가 작은 카드를 뽑아 지금까지 넣지 않은 수 중 가장 큰 수를 넣고 3) 이 과정을 반복하여 최소값을 얻을 수 있다. 최대값을 구하는 경우에는 이와 반대로 작은 수부터 가장 뒤에 넣는다.

이 방법의 유효성은 귀납적으로 증명 가능하다. 예를 들어, 최소값을 구하는 경우라면 위 방법에서 가장 앞쪽에 있는 카드에 수를 넣는 시점에 이미 그 카드보다 수가 작은 카드 외에는 아무것도 남지 않게 되므로 분할정복 방법과 동일한 수가 입력된다. 마찬가지로 두 번째로 앞쪽에 있는 카드, 세 번째로 앞쪽에 있는 카드들이 차례대로 분할정복 방법과 동일한 수를 갖게 됨을 보일 수 있

koi 카드배열 대회 풀이