백준 1874번 "스택 수열"

백준 1874번 “스택 수열”

Question:

스택 (stack)은 기본적인 자료구조 중 하나로,
컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다.
스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아
제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out)
특성을 가지고 있다.

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써,
하나의 수열을 만들 수 있다.
이때,
스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자.
임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지,
있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다.
이를 계산하는 프로그램을 작성하라.

Input:

입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다.
push연산은 +로, pop 연산은 -로 표현하도록 한다.
불가능한 경우 NO를 출력한다.

Output:

입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다.
push연산은 +로, pop 연산은 -로 표현하도록 한다.
불가능한 경우 NO를 출력한다.

Restriction:

시간제한:
2 초

Example Case: Input case 1:

8
4
3
6
8
7
5
2
1

Output case 1:

+
+
+
+
-
-
+
+
-
+
+
-
-
-
-
-

Input case 2:

5
1
2
5
3
4

Output case 2:

NO

풀이 과정: 이 문제는 스택의 성질
후입선출(LIFO)을 이해하고 코드를 작성하는게 핵심이다.

처음에 문제를 이해하는데 시간이 걸렸는데,
간단하게 입력받은 수열 자체가
1~N 까지 오름차순으로 push하는 스택에서
연산을 통해 똑같이 나올 수 있는지 물어보는 문제이다.

그래서 처음 접근한 방식은,
입력받은 수열 자체를 다른 list에 삽입 후,
1~N까지 삽입한 스택과 비교하여 풀이방향을 잡으려 했으나,
후입선출이라는 큰 성질을 잊으면 안된다.

우선,첫 번째 예제를 보면
“4”라는 element가 가장 먼저 pop이 되어야한다.
따라서,
1~4까지 push한 후,
pop을 진행하면 된다.
그 다음 element는 “3”인데,
이 또한 앞서 4까지 push후
pop연산을 진행 했기 때문에 1~3 element가 스택안에 존재한다.
그러므로 pop을 해주면된다.

주의해야할 것은,
pop할 element는 top에 존재하도록 해야한다.
그런데
두번째 예제 같이
5 3 4 순서대로 pop이면 성립이 되지않는다.
“3” element가 top이면,
4 라는 element는 이전 top보다 크기 때문에
수열을 만드는것이 불가능하다.

따라서,
pop할 element까지 순서대로 push 한 후
pop연산을 하는것이 가장 큰 풀이 방향이다.

아래는 python으로 작성한 코드이다.

stack = []
answer = []
flag = 0
cur = 1
import sys
n = int(sys.stdin.readline())
for i in range(n):
    num = int(sys.stdin.readline()) #첫 번째로 pop할 element를 입력받음
    while cur <= num: #cur = num일때까지 while문 돌기
        stack.append(cur) #직접 연산을 할 스택에 값 push
        answer.append("+") #연산의 결과를 다른 list에 저장(답)
        cur += 1 #첫 번째로 pop할 element까지 값을 증가하면서 push
    if stack[-1] == num: #top이 pop할 element와 같은 경우
        stack.pop() #직접 연산하는 스택에서 pop
        answer.append("-") #연산 결과 저장
    else: #오름차순으로 push한 element가,pop할 때 순서가 지켜지지 않는 경우
        #ex) num = 3 -> 4되는 경우,
        #이미 스택엔 3 이하로 element가 존재할 텐데 
        #그 이상의 element를 가져오지 못한다.
        #즉,top이 num보다 크면 성립이고 아니면 가져오지 못함.
        print("NO") #NO 출력
        flag = 1 #이 경우에는 연산의 결과를 출력할 필요가 없다.
        break
if flag == 0: #정상적으로 연산을 한 경우,결과 출력
    for i in answer:
        print(i)

• 백준
• 문제풀이