책너두 - 알고리즘 챌린지[1/20]

3주간 진행되는 책너두 - 무지성 알고리즘 챌린지에 참여하게 되었다.

그냥 무지성으로 가만히 있어도 문제가 계속 제공해주면 좋겠다는 저의 바람을 담아 챌린지 이름을 무지성 알고리즘 챌린지로 지어보았습니다. - 챌린지 개최자님!

혼자 공부하다가 지친 것도 있고 함께 할 때 나는 시너지가 있을 거 같아 신청하게 되었다! 요일 별로 문제 난이도가 다르지만 모든 문제를 당일에 풀어보도록 하자

---

첫 날은 스택 문제.

스택 수열

다른 분 풀이 중에 스택을 직접 구현하신 분도 계셨다. 예전에 카카오 코테를 볼 때 직접 링크드리스트를 구현해서 문제를 풀었던 기억이 있는데, 직접 구현해서 푸는 방법도 몸에 익혀두는 게 좋을 거 같다.(막상 코테 풀면 삐걱 거릴 때가 있다)

---

풀이 요약

now라는 값을 기준으로 ans 리스트에 +, -를 넣어주는 방법으로 풀었다.

"NO"를 출력하는 조건이 스택에 마지막으로 들어간 값과 일치하는 지 여부만 확인하면 되어서 편하게 풀었다

n = int(input())
nums = [int(input()) for i in range(n)]
stack = []
now = 1
ans = []
for num in nums :
    while num >= now :
        ans += "+"
        stack.append(now)
        now += 1
    if num == stack[-1] :
        ans += "-"
        stack.pop()
    
    else :
        print("NO")
        exit()

for res in ans :
    print(res)

+++

백준에서 input 값을 다음과 같이 바꿔주면, 시간복잡도를 낮출 수 있습니다! (알려주신 분 너무 감사합니다)

• vscode에 입력값을 입력한 후 (윈도우 기준)ctrl + Z 를 마지막에 입력하면 됩니다

import sys
n, *nums = map(int, sys.stdin.buffer.read().splitlines())