[파이썬] 단계별 백준 문제 풀기 - 1874 스택수열

 

문제

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

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

입력

첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.

출력

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

 

---

<<소스코드>>

n = int(input()) #제일 첫줄의 수열의 갯수
stack = [] #빈 스택 리스트 생성
result = [] # 출력하고자 하는 '+,-' 를 담아줄 빈 리스트 생성
count = 0
X = True # X라는 변수값을 True 로 설정

for _ in range(n): #수열의 길이만큼 for문 반복
    num = int(input()) #수열 리스트

    while count < num: #최초 카운트는 0, num의 숫자가 되기 전까지 그냥 계속 스택에 push(추가)한다. 
        count += 1
        stack.append(count)
        result.append("+") #push는 '+'를 출력하므로 push 할때마다 같이 '+'를 result에 더해준다.

    if stack[-1] == num: # 만약 스택의 제일 끝의 숫자가(제일 마지막에 넣은 수)가 num과 같아지면
        stack.pop() #그때 스택에서 뺀다! 
        result.append("-") #뺄때는 '-'를 출력하므로, pop 할때마다 같이 '-'를 result에 더해준다.
    else: #count가 num보다 크면, false값이 되고 break를 두어 종료한다 
        X = False
        break
#count가 num보다 크면, false가 된다. 그렇다면 내려와서 print "NO" 출력
if X == False:
    print("NO")
else: #만약 아니면, '+,-'값을 추가해놨던 result 리스트를 순서대로 출력
    for i in result:
        print(i)

 

<<결과값>>

8
4
3
6
8
7
5
2
1

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

---

내가 이해하고 싶어서 빠르게 그림으로 그려보았다. 

일단, for문/while문을 이해하는 것이 핵심인데, 

 

주어진 수열을 차례로 돈다. push 하는 값은 오름차순 순이여야 하므로, 직전에 넣은 숫자보다 더 작은 숫자를 stack에 push할 수 없다.

 

[코드설명]

num[0] = 4를 시작한다. count는 num값이 4가 되기 전까지 1,2,3을 차례로 stack에 쌓으면서(push니까 +세번 result에 추가하면서) count를 올린다. count가 4가 되면, stack에 4를 push한다(이제 result의 +는 4개).

자 이제 stack의 4를 pop으로 빼준다. 

while문의 조건은 count < num 일때 진행되므로, false가 되어 while문이 끝나고 for문으로 돌아가 num[1]부터 다시 시작한다.

num[1] = 3 이고, stack[-1] = 3 (4가 빠졌으므로 맨 위에는 3이 남음) 이 같으므로, 3도 바로 stack에서 빼준다.

이제 Result [+ + + + - - ] 이고, Count 는 그대로 4, 현재 num은 3이기 때문에 while문이 종료되고, for문으로 돌아가 그 다음 num[2]값인 6으로 간다. count(현재 4) < num(현재 6) 이므로, count가 6이 될때까지 while문이 반복되어 stack에 6이 push되고, count가 6이되면 결국 stack에서 6도 pop 빠지게 된다.

 

만약, count가 num[i]값보다 크거나, stack에서 꺼낼 수 있는 맨 위에 값이 num에 없다면, 더이상 수열을 만들 수 없으므false가 되고 break로 for문을 종료합니다.  마지막으로 false값이면 "No"를 출력하고, 그게 아니면 result값을 순서대로 출력하면 됩니다.

 

 

*주의할점: 이중 반복문의 경우 break를 하나만 쓰면 하나의 반복문만 빠져나온다! 탈출조건 잘 명시할 것