Kicksort

여기 Kickstart에서는 잘 알려진 Quicksort 알고리즘의 팬이다. Quicksort는 리스트에서 피벗 값을 하나 고르고, 나머지 값을 피벗과의 비교 결과에 따라 두 개의 새 리스트 중 하나로 옮긴 뒤, 그 두 리스트를 각각 재귀적으로 정렬한다. 그런데 알고리즘이 다른 모든 값을 두 리스트 중 한쪽으로만 몰아넣는 피벗을 고를 수도 있는데, 이러면 분할 정복 전략의 취지가 무색해진다. 이런 피벗을 최악 피벗이라 부른다.

이 문제를 피하기 위해 우리는 Kicksort라는 변형 알고리즘을 직접 만들었다. 가운데 값을 피벗으로 쓰면 좋다고들 하기에, 우리 알고리즘은 다음과 같이 동작한다:

  Kicksort(A): // A는 E개의 원소를 가진 0-indexed 리스트
    E ≤ 1이면 A를 반환한다.
    그렇지 않으면:
      빈 리스트 B와 C를 만든다.
      A[floor((E-1)/2)]를 피벗 P로 고른다.
      i = floor((E-1)/2)인 경우를 제외하고 i = 0부터 E-1까지:
        A[i] ≤ P이면 B에 append한다.
        그렇지 않으면 C에 append한다.
    Kicksort(B) + [P] + Kicksort(C)를 반환한다.
    // [P]는 P만 담은 새 리스트이고, +는 연결을 뜻한다

연습 삼아, 우리는 1부터 N까지의 수를 나열한 순열 리스트에 Kicksort를 적용해 보고 있다. 안타깝게도 Kicksort에도 Quicksort와 같은 문제가 남아 있는 듯하다. 모든 피벗이 최악 피벗이 될 수도 있다!

예를 들어 리스트 1 4 3 2를 보자. Kicksort는 4를 피벗으로 고르고, 나머지 값 1 3 2는 모두 두 새 리스트 중 하나로 들어간다. 그다음 리스트 1 3 2에 Kicksort를 호출하면 3을 고르고, 여기서도 나머지 값이 모두 두 새 리스트 중 하나로 들어간다. 마지막으로 리스트 1 2에서 1을 고르면, 나머지 값 2는 당연히 두 새 리스트 중 하나로만 들어간다. 모든 단계에서 알고리즘은 최악 피벗을 고른다. (Kicksort를 원소가 0개나 1개인 리스트에 호출하면 피벗을 아예 고르지 않는다는 점에 유의하자.)

이 문제를 더 조사할 수 있게 도와주자! 1부터 N까지의 수를 나열한 순열이 주어질 때, Kicksort가 최악 피벗만 고르는지 판별하라.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어지며, 각 테스트 케이스는 두 줄로 이루어진다. 첫 줄에는 순열의 원소 수를 나타내는 정수 N이 하나 주어진다. 둘째 줄에는 1부터 N까지의 값으로 이루어진 순열 Ai가 N개 주어진다.

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 이 리스트를 정렬할 때 Kicksort가 최악 피벗만 고르면 YES, 그렇지 않으면 NO이다.

• Ai는 1부터 N까지의 값으로 이루어진 순열이다.

예제 1은 문제 지문에서 설명한 경우이다.

예제 2에서 첫 피벗은 1이고, 이는 나머지 값 2 3 4를 모두 두 새 리스트 중 하나로 몰아넣으므로 최악 피벗이다. 그러나 리스트 2 3 4에 대한 Kicksort 호출은 3을 피벗으로 고른다. 이는 2를 한쪽 새 리스트에, 4를 다른 쪽 새 리스트에 넣으므로 최악 피벗이 아니다.

예제 3에서 Kicksort는 최악 피벗 2를 먼저 고르고, 그 뒤에는 고를 피벗이 남아 있지 않다.

예제 4에서 Kicksort는 2를 먼저 고르는데, 이는 최악 피벗이 아니다.