[백준알고리즘] 1966번 : 프린터큐, 파이썬

문제는 아래 사이트에 들어가면 확인 할 수 있다. 

www.acmicpc.net/problem/1874

1874번: 스택 수열

 

 

문제를 첨에 이해하는데 시간이 좀 걸렸다.

 

이 문제의 핵심은

 

<임의의 수열이 주어졌을때 그 스택을 이용하여 그 수열을 만들 수 있는지 여부를 판단> 해야한다.

 

 

예제 입력을 보면서 문제를 이해해보자. 

첫번째 입력 n : 수열 안 수의 개수

두번쨰 부터 n개의 줄동안 입력 : n개의 수를 나열

 

8 

[4, 3, 6, 8, 7, 5, 2, 1]

8개의 숫자가 나열된 수열임을 알려준 후, 수열 [4, 3, 6, 8, 7, 5, 2, 1]를 입력하였다.

 

스택은 컵과 같이 생긴 자료구조이다.  가장 나중에 들어간 자료가 가장 먼저 나온다. (LIFO, Last in First Out)

 

수열의 원소를 하나씩 보면서 진행한다.

현재 확인하고 있는 원소를 current라고 지칭하겠다.

 

첫번째 원소는 4이다.

current = 4

1부터 1씩 증가해가면서 스택에 넣어준다

stack : [1,2,3,4]

current 가 스택의 마지막에 있으므로 빼준다. 

stack : [1,2,3]

 

두번째 원소는 3이다. 

current = 3

먼저 들어갔던 4보다 작은 값이므로 스택에 더 넣지 못한다.

current 가 스택의 마지막에 있으므로 빼준다. 

stack : [1,2]

 

세번째 원소는 6이다. 

current = 6

4까지 들어갔었으므로 5부터 1씩 증가해가면서 6까지 스택에 넣어준다

stack : [1,2,5,6]

current 가 스택의 마지막에 있으므로 빼준다. 

stack : [1,2,5]

 

네번째 원소는 8이다. 

current = 8

6까지 들어갔었으므로 7부터 1씩 증가해가면서 8까지 스택에 넣어준다

stack : [1,2,5,7,8]

current 가 스택의 마지막에 있으므로 빼준다. 

stack : [1,2,5,7]

 

다섯번째 원소는 7이다.

current = 7

먼저 들어갔던 8보다 작은 값이므로 스택에 더 넣지 못한다.

current 가 스택의 마지막에 있으므로 빼준다. 

stack : [1,2,5] 

 

남은 원소5, 2, 1도 방금과 같은 과정을 반복해서 뺄 수 있다.

 

위의 과정을 코드로 작성하면

 

<전체코드>

반면 예제 입력 2번은 current가 스택의 마지막에 있지 않은 상황이 발생하기 때문에 수열을 생성할 수 없다.