백준 1874번 스택 수열 파이썬 풀이

Python

[Python] 백준 알고리즘 온라인 저지 1874 스택 수열

1874 스택 수열

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

1874번: 스택 수열

문제를 이해하는데 시간이 좀 걸렸다. n값을 받고 수를 차례대로 입력할 때 입력한 수까지 스택에 넣었다가 그 수를 빼서 입력받는 수열을 만들 수 있는지 출력하는 문제로 중복으로 스택에 추가되지 않는다는 점을 신경 써야 한다. 예를 들면

n = 5 (3, 5, 4, 2, 1)를 입력 받았을때 스택에 (+, +, +, -, +, +, -, -, -, -) 순으로 추가하고 빼어 입력받은 대로 수열 형성이 가능해진다.

---

코드

import sys
input = sys.stdin.readline

n = int(input())
stack = []
result = []
digit = 1
able = True

for _ in range(n):
    num = int(input())
    while digit <= num: # digit의 수를 오름차순 증가, stack 리스트에 추가
        stack.append(digit)
        result.append('+')
        digit += 1

    if stack[-1] == num: # stack 마지막 값과 입력값 같으면
        stack.pop()
        result.append('-')
    else:   # 같지 않으면 able -> false로 바꾸고 이 for문 나옴
        print('NO')
        able = False
        break
if able == True: # 가능할때 result 리스트 출력
    for i in result:
        print(i)

---

풀이 

수를 넣었다가 뺄 stack과 +, -를 저장할 result 배열 두개를 먼저 선언하고 수는 오름차순으로 1부터 올라가기에 digit을 따로 설정해준다. 그리고 결과가 false일 때 값을 확인하고 for문을 빠져나오기 위해 able값을 선언한다.

이후 코드는 어렵지 않다 오름차순으로 += 1 씩 digit을 올려가며 stack에 넣어주고 입력받은 num값과 마지막 수가 같을 때 stack에서 그 수를 빼주고 result에 -를 넣어준다.

마지막 수와 num이 같지 않을때는 수열을 만들 수 없는 경우이므로 NO를 출력하고 able을 false로 바꾼 후 for문을 빠져나온다. 하지만 끝까지 able이 True로 간다면 for문을 통해 result 즉 +,- 값이 저장된 배열을 하나씩 출력하여준다.

---

풀이 결과

1874 풀이 결과