[Python] 백준 1874 : 스택 수열

기본 스택 문제 중 하나인 스택 수열 문제를 풀어보았습니다.

 

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

1874번: 스택 수열

 

 

문제를 처음 보았을 땐 이해가 되지 않았지만 아래 힌트를 보고 풀이를 하였습니다.

제일 먼저 입력된 숫자만큼 count를 해줘서 push를 진행해 주고, 해당 숫자가 나오면 반복문을 탈출하여 pop을 진행하고 숫자를 빼내어 줍니다.

예제 1을 예로 들어보면 4가 입력 되었을 땐 스택엔 1,2,3,4가 들어가게 되고 4가 나왔으니 pop을 해주어 스택엔 1, 2, 3이 들어있습니다.

그다음으로 3이 입력이 되었으니 count를 추가하지 않고, 바로 pop을 해주어 스택엔 1, 2가 들어있습니다.

그리고 6이 입력되었을 땐 스택엔 1, 2, 5, 6이 들어가고 6이 나왔으니 pop을 진행하여 스택엔 1, 2, 5가 들어있습니다.

8이 입력되었을 땐 count가 6이므로 7, 8이 스택에 입력되고, 8이 나왔으니 pop을 진행하여 스택엔 1, 2, 5, 7이 들어있습니다.

마지막으로는 순서대로 입력을 받기 때문에 pop을 통해 수열이 완성되었습니다.

 

예제 2를 통해서 수열이 되지 못할 때의 입력을 살펴보게 되면 입력 3을 받게 될 시 4가 먼저 나오게 되어 불가능하게 판단되어 NO가 출력됩니다.

 

n = int(input())
cnt = 1
data = list()
result = list()

for i in range(n):
    input_num = int(input())
    while cnt <= input_num:	# 원하는 숫자가 나올때까지 반복
        data.append(cnt)
        cnt += 1
        result.append('+')
    if input_num == data[-1]:	# 원하는 숫자가 나와서 pop 진행
        data.pop()
        result.append('-')
    else:
        print('NO')	# 수열이 불가능할 떄 출력 후 코드 종료
        exit(0)

print('\n'.join(result))

 

 

오늘도 감사합니다.