[백준/1771] 카드 묶음 (Python)

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

 

Difficulty : Gold 2

 

Status : Solved

 

Time : 00:31:13

 

---

 

문제 설명

 

 

1 이상 N 이하의 자연수가 한 장에 하나씩 순서대로 적혀 있는 N장의 카드가 있다. 이 카드를 임의의 순서로 섞은 뒤 일렬로 배열하였다. 아래는 N = 6인 경우의 한 예이다.

[6] [3] [2] [1] [4] [5]

 

각각 N장의 카드는 하나의 묶음을 이루고 있다고 생각할 수 있다. 즉 초기에 N개의 카드 묶음이 순서대로 배열되어 있는 것이다.

만일 하나의 카드 묶음 속에 포함되어 있는 카드들이 서로 연속된 수들로만 이루어져 있으면, 그러한 묶음을 유효한 카드 묶음이라고 한다. [2], [4 5], [3 5 6 4] 등은 유효한 카드 묶음의 예이다.

인접한 두 개의 카드 묶음을 하나로 합쳤을 때 새로 생긴 카드 묶음도 유효한 카드 묶음이면, 두 카드 묶음을 하나로 합칠 수 있다. 이러한 과정을 N-1번 반복하면 N개의 카드를 하나의 카드 묶음으로 만들 수 있다. 아래는 이러한 과정의 한 예를 순서대로 보인 것이다.

 

[6] [3] [2] [1] [4] [5]
[6] [3] [2 1] [4] [5]
[6] [3 2 1] [4] [5]
[6] [3 2 1] [4 5]
[6] [3 2 1 4 5]
[6 3 2 1 4 5]

 

N장의 카드의 초기 배열이 주어졌을 때, 이러한 과정을 N-1번 반복하여 N개의 카드를 하나의 카드 묶음으로 만드는 과정을 구하는 프로그램을 작성하시오. 항상 가능한 경우만이 입력으로 주어지며, 여러 가지 해 중에서 하나만 출력하면 된다.

 

 

입력 및 출력

 

입력

 

첫째 줄에 자연수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 카드의 초기 배열을 나타내는 N개의 정수가 빈 칸을 사이에 두고 순서대로 주어진다.

 

출력

 

첫째 줄부터 N-1개 줄에 걸쳐 합치는 과정을 표현해 줄 한 개의 정수를 출력한다. 합쳐질 두 개의 묶음 중, 앞 묶음의 마지막 카드가 몇 번째 카드인지를 출력하면 된다. 예를 들어, [6] [3 2 1] [4 5]의 경우, 앞 묶음인 [3 2 1]의 마지막 카드인 1은 네 번째이므로, 4를 출력하면 된다.

 

입력 예시

 

6
6 3 2 1 4 5

 

출력 예시

 

3
2
5
4
1

 

 

---

 

풀이

 

가능한 경우밖에 주어지지 않으므로, 스택으로 그리디하게 풀이해볼 수 있다.

 

 

• 총 N개의 인덱스를 순회하며 다음 과정을 시행한다.
• 스택의 최상위 노드와 현재 노드가 연속되는 경우(스택의 최댓값보다 현재 노드값의 최솟값이 1 크거나, 스택의 최솟값보다 현재 노드값의 최댓값이 1 작을때) 다음 반복을 시행한다.
  • 스택을 pop한다
  • pop한 노드의 index를 정답으로 저장한다.
  • 현재 노드의 최댓값과 최솟값을 업데이트한다
  • 위 조건으로 돌아간다.
• 현재 노드를 스택에 삽입한다.
• 모든 순회가 끝났을 때, 스택에는 단 하나의 원소만이 남게 된다(가능한 경우밖에 주어지지 않으므로)

O(N)의 시간복잡도 내에 풀이 가능하다.

 

풀이 코드

import sys
input = sys.stdin.readline

N = int(input())
num_list = list(map(int, input().split()))
answer = []
stk = []

for i in range(N) :
  cur_min, cur_max = num_list[i], num_list[i]
  while stk and ( stk[-1][0] == cur_max + 1 or  stk[-1][1] == cur_min - 1) :
    prev_min, prev_max, prev_idx = stk.pop()
    cur_min = min(cur_min, prev_min)
    cur_max = max(cur_max, prev_max)
    answer.append(prev_idx + 1)
  stk.append((cur_min, cur_max, i))

print(*answer, sep = "\n")

풀이 완료!