백준 10828

💡문제 분석 요약

(시간/공간복잡도 제약도 추가하기)

• 5개의 명령에 대하여 각 명령에 대해 다른 작업이 수행된다.
• 명령은 5개 이외에는 주어지지 않는다.
• 입력 개수는 10만개까지 가능하다.

💡알고리즘 설계

1. 입력값을 담는 stack은 파이썬의 list를 사용하였다.
2. 5개의 명령에 대해 switch처럼 처리하는데, 파이썬은 switch가 없으므로 if-elif 형식으로 작성해본다.
3. stack이 비어있는 경우처럼 특별한 케이스가 있는 명령어에 대해선 if-else를 안쪽에 하나 더 추가해준다.

💡코드

"""
1. 처음에는 시간초과 났는데, sys.stdin.readline 으로 입력받으니까 바로 해결
2. 한줄에 몇개를 입력받는지 모르는 상황에선 a, b = input().split()처럼 하지 말고 a = input().split()으로 한다.
"""

import sys
input = sys.stdin.readline

n = int(input())
stack = []

for i in range(n):
    inst = input().split()

    if inst[0] == "push":
        stack.append(inst[-1])

    elif inst[0] == "pop":
        if len(stack) == 0:
            print(-1)
        else:
            print(stack.pop())

    elif inst[0] == "size":
        print(len(stack))

    elif inst[0] == "empty":
        if len(stack) == 0:
            print(1)
        else:
            print(0)

    elif inst[0] == "top":
        if len(stack)==0:
            print(-1)
        else:
            print(stack[-1])

 

💡시간복잡도

N개의 입력에 대해 비교하므로 O(n)이 될 것으로 예상된다. n개의 for문이 돌아가는 동안 if-elif 말고는 별다른 작업이 없고, 이 작업은 O(1)이므로 전체 시간 복잡도는 O(n)이 될 것이다.

💡 틀린 이유

1. 시간초과 때문에 계속 틀렸는데, input()으로 입력을 받아서 틀렸다. 이를 찾아보니 더 빠른 입력인 sys.stdin.readline이 있었다. 다른 코드를 그대로 두고, 이것만 바꿔주니 바로 통과되었다.
2. 시간초과 이전에는 입력받는 것에서 어려움을 겪었다. push할 때는 푸쉬할 값까지 입력받고 그 외에는 숫자가 안들어오는데 이걸 어떻게 입력받아야하는지 고민이었다. a, b = map(int, input().split())과 같이 입력을 받는 것만 습관이 되어서 오히려 쉬운 걸 헷갈린 것 같다. 단순히 lst = input().split()이라고만 해도 입력받을 수 있었다.

💡 틀린 부분 수정 or 다른 풀이

1. input -> sys.stdin.readline
2. 앞선 분들의 풀이를 보니, top = -1이라고 지정해놔서 가독성이 좋아지는듯했다. 이런 섬세함이 더 좋은 코드를 만드는듯하다.

💡 느낀점 or 기억할정보

1. top = -1처럼 가독성 좋아질 수 있는 부분 생각해서 코드에 반영하기.
2. 몇개의 입력이 들어올지 모르면 lst = input().split()이라고 해놔도 좋다.