[정글 알고리즘]-[하]-백준 10828 스택

처음엔 split() 없이 풀어보려 했다. 그게 통과는 됐는데, 시간 초과가 났다. 그 다음엔 왜 느렸는지까지 따라가 봤다.

---

문제 — 백준 10828 스택

정수를 저장하는 스택을 구현한다. 명령이 주어지면 각각 처리하고 결과를 출력한다.

항목	내용
문제 번호	백준 10828
난이도	실버 4
분류	자료구조, 스택
명령 종류	push X, pop, size, empty, top
입력 범위	명령 수 N ≤ 10,000

명령별 동작

명령	동작	출력
push X	정수 X를 스택에 넣는다	없음
pop	맨 위 원소를 꺼낸다. 비어 있으면 -1	꺼낸 값 또는 -1
size	스택에 들어 있는 원소 수	원소 개수
empty	비어 있으면 1, 아니면 0	1 또는 0
top	맨 위 원소를 확인한다. 비어 있으면 -1	맨 위 값 또는 -1

---

핵심 아이디어 — 리스트를 스택으로

파이썬 리스트는 뒤쪽에서 넣고 빼기가 O(1)이다. 스택의 "맨 위"를 리스트의 맨 뒤로 보면 된다.

스택 연산	리스트로 구현	예시
push X	stack.append(X)	[1,2] → push 3 → [1,2,3]
pop	stack.pop()	[1,2,3] → pop → 3 반환, [1,2] 남음
top	stack[-1]	[1,2,3] → top → 3 (꺼내지 않음)
size	len(stack)	[1,2,3] → 3
empty	stack == []	[] → 1, [1] → 0

---

1단계 — 가장 단순한 구현

split() 없이, sys 모듈 없이, 문자열을 통째로 받아서 처리한다.

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

for _ in range(n):
    command = input()

    if command[:4] == "push":
        num = int(command[5:])
        stack.append(num)

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

    elif command == "size":
        print(len(stack))

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

    elif command == "top":
        if stack == []:
            print(-1)
        else:
            print(stack[-1])

입력을 문자열로 받는 방식

command = input()으로 한 줄을 그대로 받으면 문자열이 저장된다.

입력	command 값
push 3	"push 3"
pop	"pop"
top	"top"

command[:4] == "push" — 슬라이싱으로 명령 구분

파이썬 문자열은 인덱스로 자를 수 있다. 문자열[시작:끝] 형태로 쓰면 잘라낸 부분 문자열이 나온다.

command = "push 3"

# 문자 인덱스
# p=0  u=1  s=2  h=3  ' '=4  3=5

command[:4]   # "push"
command[5:]   # "3"

슬라이싱	의미	"push 3"일 때 결과
command[:4]	앞 4글자	"push"
command[5:]	6번째 글자부터 끝까지	"3" → int() 씌우면 정수 3

command == "push"로 비교하면 "push 3"이 들어왔을 때 False가 된다. 뒤에 숫자가 붙기 때문이다. 그래서 앞 4글자만 잘라서 비교한다.

각 명령어 구현 설명

if command[:4] == "push":
    num = int(command[5:])  # "3" → 3
    stack.append(num)        # 스택 맨 뒤에 추가

push: 숫자를 꺼내 스택에 넣는다.

elif command == "pop":
    if stack == []:
        print(-1)
    else:
        print(stack.pop())  # 맨 뒤 원소를 꺼내고 반환

pop: 빈 리스트에서 pop()을 호출하면 오류가 나므로 반드시 먼저 확인한다.

elif command == "top":
    if stack == []:
        print(-1)
    else:
        print(stack[-1])  # 꺼내지 않고 마지막 값만 확인

top: stack[-1]은 맨 뒤 원소를 꺼내지 않고 읽기만 한다. pop()과 다르다.

동작 시뮬레이션

입력이 아래와 같을 때 스택이 어떻게 변하는지 따라가 본다.

7
push 1
push 2
top
size
empty
pop
pop

명령	처리	스택 상태	출력
push 1	append(1)	[1]	—
push 2	append(2)	[1, 2]	—
top	stack[-1]	[1, 2]	2
size	len(stack)	[1, 2]	2
empty	stack == []?	[1, 2]	0
pop	stack.pop()	[1]	2
pop	stack.pop()	[]	1

---

2단계 — 시간 초과 원인 분석

1단계 코드를 제출하면 시간 초과가 난다. 이유는 두 가지다.

원인 1 — input()이 느리다

파이썬의 input()은 내부적으로 처리가 많아 명령이 수천 개 이상일 때 느려진다.
sys.stdin.readline()은 버퍼에서 직접 읽어서 더 빠르다.

원인 2 — print()를 매번 호출하면 느리다

출력 명령이 많으면 print()를 반복적으로 호출하는 것 자체가 부담이 된다.
결과를 리스트에 모아두었다가 마지막에 한 번만 출력하면 빠르다.

구분	느린 방식	빠른 방식
입력	input()	sys.stdin.readline()
출력	print() 매번 호출	result.append() 후 마지막에 한 번

readline()과 rstrip() 이해

sys.stdin.readline()은 줄 끝에 \n이 붙어서 들어온다. 이것을 제거해야 조건 비교가 제대로 된다.

sys.stdin.readline()        # "push 3\n"  ← \n이 붙어 있음
sys.stdin.readline().rstrip() # "push 3"   ← rstrip()으로 오른쪽 공백·줄바꿈 제거

함수	동작	"pop\n" 에 적용하면
rstrip()	오른쪽 공백·줄바꿈 제거	"pop"
strip()	양쪽 공백·줄바꿈 제거	"pop"

결과 모아서 한 번에 출력하는 방식

# 느린 방식 — 출력이 생길 때마다 호출
print(stack.pop())   # 매번 I/O 발생

# 빠른 방식 — 리스트에 쌓아두었다가 마지막에 한 번
result.append(str(stack.pop()))
# ...
sys.stdout.write("\n".join(result))  # I/O 1번만 발생

"\n".join(result)는 리스트 원소들을 줄바꿈 문자로 이어 붙여 하나의 문자열로 만든다.

result = ["2", "2", "0", "2", "1"]
"\n".join(result)
# "2\n2\n0\n2\n1"
# 출력하면
# 2
# 2
# 0
# 2
# 1

---

최종 코드

1단계 코드 구조를 그대로 유지하면서 느린 부분 두 곳만 교체했다.

# 스택 — 백준 10828
# https://www.acmicpc.net/problem/10828
import sys

n = int(sys.stdin.readline())
stack = []
result = []

for _ in range(n):
    command = sys.stdin.readline().rstrip()

    if command[:4] == "push":
        num = int(command[5:])
        stack.append(num)

    elif command == "pop":
        if stack == []:
            result.append("-1")
        else:
            result.append(str(stack.pop()))

    elif command == "size":
        result.append(str(len(stack)))

    elif command == "empty":
        if stack == []:
            result.append("1")
        else:
            result.append("0")

    elif command == "top":
        if stack == []:
            result.append("-1")
        else:
            result.append(str(stack[-1]))

sys.stdout.write("\n".join(result))

1단계 vs 최종 — 달라진 곳

항목	1단계 (시간 초과)	최종 (통과)	이유
입력	input()	sys.stdin.readline().rstrip()	readline이 더 빠름 + \n 제거
출력 방식	print() 바로 호출	result.append() 후 일괄 출력	I/O 횟수를 1번으로 줄임
출력 호출	print(값)	sys.stdout.write("\n".join(result))	버퍼에 한 번에 씀
알고리즘	동일	동일	로직은 전혀 안 바뀜

result에 값을 넣을 때는 반드시 str()로 문자열 변환을 해야 한다.
"\n".join()은 문자열 리스트만 처리할 수 있어서, 정수가 섞여 있으면 TypeError가 난다.

---

초보자가 자주 하는 실수

실수	틀린 코드	올바른 코드
빈 스택에서 pop	stack.pop() 바로 호출	먼저 stack == [] 검사
push 숫자를 문자열로 넣기	stack.append(command[5:])	stack.append(int(command[5:]))
push 비교를 ==으로	command == "push"	command[:4] == "push"
result에 정수 그대로 넣기	result.append(stack.pop())	result.append(str(stack.pop()))
rstrip() 빠뜨리기	readline()만 씀	readline().rstrip()

---

시간복잡도

연산	복잡도	근거
push (append)	O(1) 평균	리스트 맨 뒤 추가
pop (pop)	O(1)	리스트 맨 뒤 제거
size (len)	O(1)	파이썬 리스트는 길이를 별도 저장
empty, top	O(1)	인덱스 접근 또는 len 비교
전체 (N개 명령)	O(N)	각 명령이 O(1)

---

코드 로직은 처음부터 맞았다. 달라진 건 입력과 출력 방식뿐이었다. 알고리즘이 맞아도 I/O에서 시간 초과가 나는 경우가 있다는 걸 이번에 확인했다.

🌿