[백준] Python - 1874 스택 수열

처음엔 문제 이해가 너무 되지 않아서.. 어려웠고, 이후엔 시간 초과가 계속 떴다 ㅠ 수정하다보니 불필요한 계산이 있었다는 것을 알게 되어서 수정하니 통과되었다!

 

---

 

문제 링크

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

1874번: 스택 수열

 

문제 풀이

1. m = [ 4, 3, 6, 8, 7, 5, 2, 1 ] 을 순회하면서
2. 그 숫자(ex. 4) 만큼 l.append() 해준 뒤, count += 1을 한다. (이미 추가한 숫자는 이후에 제외하고 이후 숫자부터 추가하기 위함)
3. l 리스트의 마지막 숫자가 해당 숫자면 (ex. 4) pop()을 한다.
4. 아니라면 "NO"를 리턴한다.

 

전체 코드

from collections import deque

def check() :
    n = int(input())
    m = [int(input()) for _ in range(n)]
    l = deque()
    count = 0
    result = ""

    for i in m :
        while count < i :
            count += 1
            l.append(count)
            result += '+\n'
        
        if l[-1] == i :
            l.pop()
            result += '-\n'
        else :
            return "NO"

    return result

print(check())