[알고리즘][파이썬] 백준_1874_스택 수열

https://www.acmicpc.net/problem/1874

1874번: 스택 수열

문제를 이해하는데 시간이 오래 걸렸다!

 

n개의 숫자를 입력 받아,

1부터 숫자에 해당하는 값 만큼 PUSH한다.

예를 들어 첫 번째 수가 4라면,

1, 2, 3, 4를 차례대로 PUSH하여 각각 '+' 출력!

PUSH한 값이 4와 같아지면,

4를 POP하여 '-' 출력!

 

4 다음 수가 4 보다 작으면,

예를 들어 3이라면,

3도 POP하여 '-' 출력!

 

만약 4 다음 수가 2라면,

4와 2사이에 3이 존재하기 때문에

스택(stack)에서는 2를 POP할 수 없다.

따라서 "NO"를 출력!

 

만약 4 다음 수가 6이라면,

5, 6을 각각 PUSH, 각각 '+' 출력!

PUSH한 값이 6과 같으면,

6을 POP하여 '-' 출력!

 

글 보다 그림을 보면 이해가 쉽다!

스택 PUSH/POP에 따른 출력 결과

 

---

스택 수열 제출 코드

# 스택 수열(결과: 맞았습니다!)
n = int(input())

num = []
for _ in range(n):
    num.append(int(input()))

stk = []
rst = []
chk = 0
for i in num:
    if i > chk:
        for j in range(chk+1, i+1):
            stk.append(j)
            rst.append('+')
        chk = i
    if i != stk[-1]:
        rst = 'NO'
        break
    elif i == stk[-1]:
        stk.pop()
        rst.append('-')

if rst.count('NO') >= 1:
    print(rst)
else:
    for i in rst:
        print(i)

 

처음에는 하나의 숫자를 넣으면 '+' 또는 '-'를 출력해주는 함수를 만들어 사용해 봤다.

그 결과 예제 입력 1은 잘 처리되었는데,

예제 입력 2에서 'NO'만 출력하도록 처리하고자 할때

오히려 코드가 복잡해 졌다.

 

해결한 방법은

함수를 생성하지 않고,

rst 리스트를 생성하여 PUSH, POP이 일어날때

'+, -, NO'를 각각 append 한 후,

출력 폼에 맞게 rst(result) 리스트를 출력하는 방법을 썼다.

rst 리스트에 'NO'가 하나라도 있으면,

최종 출력은 'NO'만 출력되도록 했다.

 

앞선 숫자에서 이미 PUSH된 숫자를

다음 숫자에서 다시 PUSH하지 않도록 하기 위해

chk(check)라는 변수를 두었다.

 

예를 들어 4에 해당하는 1, 2, 3, 4가 append 되었다면,

다음 숫자가 6일때 이미 append 된 1, 2, 3, 4를 제외한

5, 6이 차례로 append 되어야 하기 때문이다.