Notion에서 작성한 글이라, 여기에서 더 깔끔하게 보실 수 있습니다! 😮😊

---

[Challenger] 스택 수열

[스택 수열]

Solution. $O(n)$

def solve():
    stack = [1]
    ret = ['+']
    cur = 2

    for a in seq:
        while cur <= a:
            stack.append(cur)
            cur += 1
            ret.append('+')
        if stack.pop() != a: return 'NO'
        ret.append('-')
    
    return '\n'.join(ret)

seq = [int(input()) for _ in range(int(input())]
print(solve())

• 일단 수열을 이루는 각 원소 $A_i$에 해당하는 값을 push할 수 있을 때까지($cur \le a)$ 계속해서 push해주고 나면,
• pop을 해주는데 그 값이 $A_i$가 아니라는 것은 ‘스택 수열’을 만들 수 없다는 의미이므로 바로 'NO'를 반환한다.

---

Memo

• 일단 정답 코드를 짜는 데에는 그렇게 오래 걸리지 않았는데, 코드를 깔끔하게 다듬는 과정에서 꽤 시간을 소모했다..
  • 머릿속으로만 했던 생각을 순서도로 그려보거나 의사코드를 끄적거리면서 나름대로의 검증을 거치는 과정이 정말 나에게 많은 도움이 된 것 같다. 이 부분도 계속 이렇게 열심히 하고,
  • 구현 문제들을 좀 풀어봐야겠다고 느꼈다. PS를 처음 시작할 땐 당장 알고리즘을 모르기도 했고, 언어에 익숙하지도 않아서 단순 구현 문제들을 이것저것 많이 풀어봤었다.
  • 내가 생각하는 바를 코드로 온전히 녹여내기가 어려웠던 당시, 약간의 아이디어만 있다면 구현으로 풀리는 문제들을 잡고 늘어지면서 점점 코드를 어떻게 짜야 하는지 배워갔던 것 같다. 풀어봐야지!