[실버 II] 1874번. 스택 수열

 문제 

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

1874번: 스택 수열

 사용 언어 

Python3

 풀이 과정 

스택은 이제 잘 알고 친숙한 자료형이라고 생각했는데 문제로 풀려니 또 바로 풀리진 않았다. 사실 문제를 이해하는데에도 시간이 좀 걸렸는데 (문제 설명이 불친절한 것 같다) 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓는다는게.. +를 하면 1부터 스택에 들어가고 -를 하면 스택의 성질대로 맨 위의 원소가 pop된다.

 

원하는 수열을 만들기 위해 -가 필요할 때는 현재 스택의 마지막 원소와 비교하면 되지만, 원하는 수가 나올 때까지 +할 때의 로직을 생각하는데 약간 어려움이 있었다. 그래도 차분히 생각해서 while문으로 구현 완료!

 

생각보단 시간이 걸렸지만 맞았습니다!!

 

 제출 답안 

from sys import stdin
input = stdin.readline

n = int(input())
stack = []
answer = []
cur = 1

for i in range(n):
    num = int(input())
    while cur <= num:
        stack.append(cur)
        answer.append("+")
        cur += 1

    if num == stack[-1]:
        stack.pop()
        answer.append("-")
    else:
        print("NO")
        exit()

print(*answer, sep = "\n")

 

 다른 사람 코드 

1. 맞힌 사람 중 시간이 가장 짧은 코드이다. 그만큼 메모리를 사용한 듯 하다.

import sys

input = sys.stdin.read


def sol1874():
    n, *nums = map(int, input().split())
    cur = 1
    st = []
    answer = []
    for num in nums:
        while cur <= num:
            st.append(cur)
            answer.append('+')
            cur += 1
        if st[-1] != num:
            answer = ['NO']
            break
        st.pop()
        answer.append('-')
    print('\n'.join(answer))
   

if __name__ == '__main__':
    sol1874()

➡ 특이하게 readline이 아니라 read를 사용해서 n과 nums를 한 줄로 입력받았다. 처음 보는 방식! 그 외에는 if문에서 "NO" 출력 경우를 처리하고 아닐 경우 -를 추가하는 로직으로 사용한 것과 답안 출력 방식에 언패킹이 아니라 join을 사용한 것, 함수로 묶어 호출한 차이정도인데 내 코드와 꽤 많이 차이가 난다.

 

가장 미스터리인 점은 로직이 똑같아 보이는데 메모리를 확실히 더 많이 쓴다는 것..? 내 코드에 하나씩 적용하며 비교해봐야겠다.