[백준/13415] 정렬 게임 (Python)

Problem : https://www.acmicpc.net/problem/13415

13415번: 정렬 게임

 

Difficulty : Gold 1

 

Status : Solved

 

Time : 00:20:47

 

---

 

문제 설명

 

 

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

예를 들어, 과제로 주어진 수열이 [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개의 세트를 모두 진행하고 난 뒤 수열의 모든 원소를 출력한다.

 

입력 예시

 

4
4 1 2 3
1
3 2

 

출력 예시

 

2 1 4 3

 

 

---

 

풀이

 

1. 모든 과정 후 정렬이 어떤 형태로 이루어졌을지 고민해보자. 아마도 (오름차순 - 내림차순 - 오름차순 ... ) 모양 혹은 (내림차순 - 오름차순 - 내림차순 ... ) 형태로 이루어졌을 것이다. 앞선 정렬값 중 현재 정렬 범위보다 좁은 정렬은 전부 무시되므로 스택 형태로 구현해 볼 수 있겠다.

 

2. 한 번의 순회 끝에, 정렬 스택은 범위에 대한 내림차순으로 정렬되어 있다. 우리는 직관적으로 스택 맨 처음에 제시된 구간 이내의 값들만을 원래 리스트에서 정렬해주면 됨을 알 수 있다. 이 값들을 복사하여, 덱 형태로 정렬해주자. 이를 숫자 덱이라고 명명하자.

 

3. 정렬 스택의 우선순위는 앞선 값이 먼저이다. 즉 i번째 정렬 스택의 값이 오름차순이라면, 숫자 덱의 큰 값부터 pop하여 배치한다. 내림차순이라면 숫자 덱의 작은 값부터 pop하여 배치하도록 한다. 말로 설명하려니까 좀 어려운데... 이 문제는 풀이는 매우 직관적이지만 막상 설명하기가 더 까다로운 문제인 것 같다.

 

총 시간복잡도는 정렬에 소요되는 O(NlogN)이 될 것이다.

 

풀이 코드

from collections import deque
import sys
input = sys.stdin.readline
N = int(input())
nums = list(map(int, input().split()))
K = int(input())
stk = []
for i in range(K) :
  a, b = map(int, input().split())
  for j, k in [(a-1, 1), (b-1, -1)] :
    while stk and stk[-1][0] <= j :
      stk.pop()
    stk.append((j, k))

stk.append((-1, 0))
sorted_nums = deque(sorted(nums[:stk[0][0]+1]))
for i in range(len(stk)-1) :
  cur, cur_d = stk[i]
  nxt, _ = stk[i+1]
  for j in range(cur, nxt, -1) :
    n = sorted_nums.pop() if cur_d == 1 else sorted_nums.popleft()
    nums[j] = n

print(*nums)

풀이 완료!