백준 알고리즘: 1874번 스택 수열 (Python)

문제 정보

---

1874번: 스택 수열

 

 

핵심

---

이 문제를 푸는것에 그래도 약 30분? 정도 걸렸던 것 같다

문제 난이도가 조금 있다고 생각하고 문제를 풀어가니 어떻게 접근해야될 지 몰랐는데, 막상 풀면서 보니 술술 풀려서 신기했다

 

스택의 구조상 Last In First Out으로 마지막에 들어온 요소가 첫번째로 나갈 수 있다

파이썬의 리스트로 스택을 만들고, 1부터 차례대로 append() 시키면서 주어진 숫자가 리스트의 마지막에 들어올때까지 반복한다

리스트에 들어왔다면 pop() 의 반환값이 주어진 숫자와 맞는지 확인한다

 

이후 주어진 숫자와 마지막으로 스택에 들어간 요소와의 비교를 통하여 스택에 다음 숫자를 추가할 것인지, 아니면 다음 요소를 빼낼 것인지를 판단하면 된다

 

 

풀이

---

import sys

N = sys.stdin.readlines()[1:]
stack = []
i = 1
result = []
state = True

for n in N:
    n = int(n.strip())

    while i <= n:
        stack.append(i)
        i += 1
        result.append('+')

    if stack.pop() != n:
        state = False
        break
    else:
        result.append('-')

print('\n'.join(result)) if state else print('NO')

stack - 입력된 수열이 만들어질 수 있는지 판별할 스택

i - 1부터 n까지의 수를 차례대로 스택에 추가하기 위한 변수

result - 입력된 수열을 만들기 위해 필요한 연산의 배열

 

 

고찰

---

백준 실버2 티어에 해당하는 문제인데, 그래도 생각보다 쉽게 푼것 같아 뿌듯하다

 

배열 출력시(길이가 긴 배열일 때) ''.join() 이 for loop 로 출력하는 것보다 빠른 실행시간을 가지고 있음

print('\n'.join(result)) if state else print('NO')

print(*result, sep='\n') if state else print('NO')

 

처음에는 result 를 문자열로 두고, 문자열에 + 와 - 를 추가해주는 식으로 문제를 풀었었는데 실행시간이 너무 높은 수치가 나와서 배열로 바꾸었더니 훨씬 빠르고 효율적이었음

 

참고

---

GitHub - dduneon/CodingTestPy

소스 코드는 백준 1084: 스택 수열 을 참고하세요!