백준 1874번: 스택 수열 (Python)

접근

코드가 어렵다기 보다는 이 문제가 의미하는 것이 무엇인지를 몰라 헤메다가 다른 글의 도움을 받았다..

예제 입력 코드를 예시로 들어 어떤 과정으로 스택 수열이 표시가 될 수 있는지 확인해 보려고 한다.

push를 하면 1부터 오름차순의 순서대로 숫자를 stack에 쌓는다는 점을 유의하면서 아래 과정을 확인해보자.

먼저 첫번째 입력은 정수의 수를 입력받고 두번째 입력받는 수는 4이다.

그럼 stack의 top (stack[-1]) 이 입력받은 4가 될 때까지 push 해준다. push 해줄 때마다 별도의 list에 '+' 문자를 저장해준다.

# push
stack = [1]
op = ['+']

# push
stack = [1, 2]
op = ['+', '+']

# push
stack = [1, 2, 3]
op = ['+', '+', '+']

# push
stack = [1, 2, 3, 4]
op = ['+', '+', '+', '+']

stack의 top이 입력받은 4가 되었을 때 stack.pop()을 진행한다.

# pop
stack.pop()
stack = [1, 2, 3]
op = ['+', '+', '+', '+', '-']

다음 입력받은 숫자는 3이고, 이미 4까지 push를 했기 때문에 더이상 push는 하지 않고 stack의 top과 3을 비교한다. (push는 오름차순으로만 진행할 수 있기 때문에 다음 push는 5를 추가하게 된다.)

이때 stack의 top과 3을 비교하여 일치하면 stack.pop()을 수행하고, 일치하지 않을 경우 스택 수열이 불가능하다고 표시하면 된다.

# pop, stack의 top과 3이 일치하므로 pop을 수행
stack.pop()
stack = [1, 2]
op = ['+', '+', '+', '+', '-', '-']

다음 입력받은 수는 6이므로 stack의 top이 6이 될 때까지 push를 수행하고, stack의 top이 6이 되면 pop을 수행해준다.

# push * 2
stack = [1, 2, 5, 6]
op = ['+', '+', '+', '+', '-', '-', '+', '+']

# pop
stack = [1, 2, 5]
op = ['+', '+', '+', '+', '-', '-', '+', '+', '-']

이 같은 과정을 반복하여 수열 끝까지 스택 수열 조건에 반하지 않고 진행될 경우 op를 순서대로 표시하고, 스택 수열이 불가능할 경우 NO를 출력하면 된다.

코드

import sys

n = int(sys.stdin.readline())
stack = []
op = []
count = 1
isstackarray = True
for i in range(n):
    num = int(sys.stdin.readline())
    while count <= num:
        stack.append(count)
        op.append('+')
        count += 1
    if stack[-1] == num:
        stack.pop()
        op.append('-')
    else:
        isstackarray = False
if isstackarray == False:
    print('NO')
else:
    for j in op:
        print(j)

더 생각해 볼 것?

스택 수열이 무엇인지 모르는 채로 문제를 읽으니 아무리 읽어도 이해가 되지 않았다. 알고리즘 문제에 어떤 개념들이 있는지 다 파악할 때까지 최대한 다양한 문제를 경험해봐야 겠다는 생각을 하게 되었다. 적어도 개념을 몰라서 시도 자체를 못하는 경우는 없도록..!

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!