[13415] 정렬 게임 Success

문제

즐거운 컴퓨터 프로그래밍 시간! 이번 시간의 수업 내용은 정렬이었다. 학생들은 오름차순 또는 내림차순으로 입력받은 값을 정렬해보기 시작하였다. 수업이 끝나갈 무렵, 오늘도 어김없이 조교의 과제가 주어졌다. 과제 이름은 정렬 게임. 과제 내용은 다음과 같다. 처음에 임의의 수열이 있고, 처음 위치부터 지정된 위치까지 오름차순, 내림차순, 오름차순, 내림차순, … 의 순서를 반복하여 정렬하였을 때, 어떠한 수가 나타나는지 출력하는 프로그램을 작성하는 것이었다.

예를 들어, 과제로 주어진 수열이 [4,1,2,3] 이고, 처음 위치부터 3번째 원소까지 오름차순, 그 다음 2번째 원소까지 내림차순으로 정렬한 결과를 출력하라고 할 경우를 보자. 처음 오름차순 정렬을 수행하면 [1,2,4,3] 이 되고, 여기서 2번째 원소까지 내림차순으로 정렬하면 [2,1,4,3] 이 된다. 그리고 이것이 최종 정답이 된다. 정렬 게임에서 오름차순, 내림차순을 1번씩 하는 것을 한 세트를 진행했다고 정의한다. 수열과 K개의 세트가 주어질 때, 최종 수열을 출력하는 프로그램을 작성하시오.

입력

입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 수열의 개수 N이 주어진다. (1 ≤ N ≤ 100,000)

입력의 두 번째 줄에는 N개의 수열의 원소가 공백으로 구분되어 주어진다. 수열의 원소는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이다.

입력의 세 번째 줄에는 세트의 개수 K가 주어진다. (1 ≤ K ≤ 100,000)

입력의 네 번째 줄부터 한 줄에 한 개씩 오름차순, 내림차순을 하는 구간을 뜻하는 두 수 A, B가 주어진다. 이는 1번째 원소부터 A번째 원소까지 오름차순 정렬을 한 후, 1번째 원소부터 B번째 원소까지 내림차순 정렬을 해야함을 의미한다.

출력

출력은 표준 출력을 사용한다. 입력받은 데이터에 대해, K개의 세트를 모두 진행하고 난 뒤 수열의 모든 원소를 출력한다.

접근

• 힙정렬
• 스택

이 문제의 큰 함정은 입력된 정렬 명령을 그대로 수행하면 시간 초과에 빠지는 것입니다.

그렇기 때문에 입력된 명령을 한 번 걸러서 필요한 명령만 남기는 로직과, 그 걸러진 명령들을 가지고 최소한의 동작으로 정렬하는 로직 총 두 가지 로직이 필요합니다.

• 입력된 명령 필터링
• 최종 정렬 수행

입력된 명령 필터링

입력된 데이터 A, B에서 B가 A 보다 크다면 A의 수행은 B의 수행에 의해 묻히기 때문에 불필요합니다.

비슷한 맥락으로 다음과 같은 경우, 세 번째 줄의 이전 명령들은 불필요 해집니다.

1 2
3 2
3 4

즉 명령 필터링을 위해 명령들을 아래에서 훑어가며 스택에 넣어줍니다.

이때 스택에 들어갈 조건은 이전에 훑었던 명령보다 큰 값을 가져야 하다는 것입니다.

1 2
2 3
8 7
1 2
3 4

만약 위처럼 명령들이 입력되면 아래부터 스택에 넣는다면 다음과 같아집니다.

|          |
|ASC, 8    |
|DESC, 7   |
|DESC, 4   |
|__________|

• [8 7]이 입력된 경우 A>B 이니 둘 다 스택에 넣지만 수행 순서 역순으로 넣어야 하기 때문에 7먼저 스택에 넣습니다.

여기서 끝이 아니라 한 가지 조건이 더 있습니다. 이전에 스택에 들어간 명령과 같은 수행 값(오름차순, 내림차순)을 가지면 중복되는 부분이 생기기 때문에 바로 이전 명령을 스택에서 버리고 현재 명령을 넣습니다.

예로 스택에 [내림차순, 4] 명령이 있고 현재 [내림차순, 7] 명령을 검토 중이라면, 나중에 명령 수행 시 1~7를 내림차순 정렬하고 또 1~4을 내림차순 정렬을 하게 되기 때문에 앞서 스택에 있는 명령 [내림차순, 4]는 버리고 현재 명령인 [내림차순, 7]만 살립니다.

이 부분도 검토 로직에 포함하면 최종적으로 다음과 같아집니다.

|          |
|ASC, 8    |
|DESC, 7   |
|__________|

많은 명령어가 두 번의 수행으로 줄었습니다.

여기서 이 두 번의 명령어를 다 수행하지 않고 더 효율적인 방법을 찾습니다.

여기까지 하면 시간초과 뜹니다.(java 기준 내 코드 기준)

최종 정렬 수행

|          |
|ASC, 8    |
|DESC, 7   |
|__________|

이 명령어를 수행해야 하는 배열이 다음과 같다고 가정합니다.

1 2 3 4 5 6 7 8 9 10

그렇다면 8 이후의 9, 10은 수정되지 않습니다.

7과 8사이는 오름차순 정렬, 1~7까지는 내림차순으로 정렬됩니다.

저는 다음처럼 로직을 작성했습니다.

• 우선 명령이 미치는 최대 범위를 오름차순 정렬한다. (명령 내용과 관계없음, 어떤 알고리즘으로 정렬했는지는 아래에 있습니다.)
• 그 후 새로운 스택(arrStack)에 명령어에 맞춰 최대값 순, 최소값 순으로 수를 넣는다.
  • ASC, 8이라면 다음 명령어의 위치 값인 7 전까지 최대값부터 스택에 (8-7)개의 수를 넣습니다.
  • DESC, 7은 다음 명령어가 없으니 1까지 최소값부터 스택에 넣습니다. 즉 나머지 수 전체를 스택에 넣습니다.

여기까지 하면 새로 작성한 스택(arrStack)은 다음과 같아집니다.

|  |
|7 |
|6 |
|5 |
|4 |
|3 |
|2 |
|1 |
|8 |
|__|

• 차례로 pop하고 뒷 부분을 원본 배열과 합치면 7, 6, 5, 4, 3, 2, 1, 8, 9, 10으로 입력된 명령어대로 수행한 것 처럼 나옵니다.

상세 정렬 알고리즘

저는 제자리 힙 정렬을 이용해 정렬했습니다.

위의 로직대로라면 오름차순으로 정렬하는 알고리즘만 필요합니다.

정렬 부분 코드는 다음과 같습니다.

주의할 점으론 배열을 이용해 힙을 사용하기 때문에 배열의 시작 인덱스는 1부터 입니다.

전체 Solution

Order - 명령 저장을 위한 클래스

Solution - 문제 해결을 위한 메소드를 가진 클래스

Sort - 위에서 첨부했던 정렬 부분 클래스

Main - 참고

결과

사용 연어: Java 11

감사합니다.

Text by Chaelin. Photographs by Chaelin, Unsplash.