백준 10828 : 스택 (+파이썬에서 switch-case 구현)

더 많은 풀이

Algorithms & Data structures

 

 

📐 문제 요약

---

입력 커맨드에 따라 스택에 push, pop 등을 구현하는 문제

• 입력

첫째 줄 : 커맨드 실행 횟수 (1 ≤ N ≤ 10,000)

n번: 커맨드

• 출력

빈 스택에 대하여 커맨드가 모두 실행된 후의 스택

• 예시

size - 스택 길이 출력 empty - 비어있는지 여부 체크 (yes-1, no-0)

pop - 스택 최상단 제거 top - 스택 최상단 출력 push 123 - 스택에 숫자 123 쌓기

 

📐 문제 풀이

---

1. 사용한 자료구조 및 알고리즘
   • 스택
2. 소스 코드 및 문제 풀이

방법 1은 단순 if-else문을 활용, 방법 2는 switch-case문을 파이썬 딕셔너리로 유사하게 구현해보았습니다.

 

• 4배 빠른 검색 시간

소모된 시간을 보면 속도가 4배 이상 차이가 난다는 걸 알 수 있는데요, 그 이유는 if-else문은 원하는 조건이 나올 때까지 순차적으로 “모든” 경우를 비교하지만, 딕셔너리로 구현된 switch-case 구문은 Hash table로 구현되어 전체 데이터의 검색이 필요없기에 원하는 곳으로 한번에 이동이 가능합니다.

 

• 장점과 단점의 조합

파이썬에는 switch - case 문이 없어서 비슷하게 딕셔너리로 구현해보았습니다. 코드는 훨씬 길어졌지만 실행문과 선언분이 확실하게 분리되어 가독성이 좋아지는 것 같습니다.

하지만 아래 방법1,2 모두 코드 정답을 반환합니다. 전체 프로그램 성능에 크리티컬하게 영향을 미치는지 고민해보고 선택하는 단계가 필요할 것 같습니다.

# 방법 1. 

# 메모리: 116608KB
# 시간: 164MS

import sys

input = sys.stdin.readline

N = int(input())
res = []
for _ in range(N):
    cmd = input().split()
    action, num = None, None
    
    if len(cmd) == 1:
        action = cmd[-1]
    else: 
        action, num = cmd
        
    if action == 'push':
        res.append(num)
        
    elif action == 'pop':
        if res:
            print(res.pop())
        else:
            print(-1)
    elif action == 'size':
        print(len(res))
    elif action == 'empty':
        if res:
            print(0)
        else:
            print(1)
    elif action == 'top':
        if res:
            print(res[-1])
        else:
            print(-1)

# 방법 2. 

# 메모리: 30616KB
# 시간: 44ms

import sys

input = sys.stdin.readline

def push(res, num):
    res.append(num)
    return res
    
def pop(res):
    if res:
        print(res.pop())
    else:
        print(-1)
    return res
    
def size(res):
    print(len(res))
    return res

def empty(res):
    if res:
        print(0)
    else:
        print(1)  
    return res
        
def top(res):
    if res:
        print(res[-1])
    else:
        print(-1) 
    return res

cmd_dict = {
    "push": push,
    "pop": pop,
    "size": size,
    "empty": empty,
    "top": top
}

N = int(input())
res = []
for _ in range(N):
    cmd = input().rstrip().split()
    if len(cmd) == 1:
        action = cmd[0]
        res = cmd_dict[action](res)
    else:
        action, num = cmd
        res = cmd_dict[action](res, num)