[Baekjoon] 백준 10828. 스택

🔗 문제 링크 - 백준 10828. 스택

문제 단계	정답 여부	시간 제한	메모리 제한
🥈실버4	오답	0.5초	256MB

문제

정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 다섯 가지이다.

• push X: 정수 X를 스택에 넣는 연산이다.
• pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 스택에 들어있는 정수의 개수를 출력한다.
• empty 스택이 비어있으면 1, 아니면 0을 출력한다.
• top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

예제

입력

14
push 1
push 2
top
size
empty
pop
pop
pop
size
empty
pop
push 3
empty
top

출력

2
2
0
2
1
-1
0
1
-1
0
3

---

풀이

🔎 문제 분석

• 문제의 인풋 : 명령의 수 N (1 ≤ N ≤ 10,000), N개의 명령 (정수 X에 대하여, 1 ≤ X ≤ 100,000)
• 구하고자 하는 것 : 정수를 저장하는 스택을 구현한 후, 이에 대해서 입력으로 명령이 주어질 때마다 한 줄에 하나씩 수행

💡 풀이 핵심 아이디어

명령 개수만큼 for문을 돌리면서, 각 명령에 대한 출력값을 바로 출력할 수 있도록 조건식을 사용해야 한다.

💡 알고리즘 설계

1. 명령 개수(n)입력받기
2. 빈 스택(stack) 생성하기
3. 명령 개수(n)만큼 for문 돌리면서 다음 명령 수행:
   1. 명령(cmd)을 입력받고 공백 기준으로 분리해서 리스트화 (push X 명령때문에)
   2. 명령에 따라 조건식을 작성하고 바로바로 출력하기

💻 나의 풀이 (오답)

n = int(input()) # 명령의 수
order = [list(input()) for _ in range(n)] # 명령 입력

stack = [] # 빈 스택 생성

for i in order:
    if i[0:4] == "push":
        X = int(i[5:])
        stack.append[X]

    if i == "pop":
        print(stack.pop())

    if i == "size":
        print(len(stack))

    if i == "empty":
        if len(stack) == 0:
            print(1)
        else:
            print(0)

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

💻 나의 풀이 (정답)

import sys
n = int(sys.stdin.readline()) # 명령 개수
stack = [] # 빈 스택 생성

for _ in range(n): # 각 명령 별 반복 수행
        cmd = list(sys.stdin.readline().split()) # 명령을 입력받고 공백 기준으로 분리해서 리스트화

        # 명령1. push X
        if cmd[0] == 'push':
                stack.append(cmd[1])

        # 명령2. pop
        elif cmd[0] == 'pop':
                if len(stack) != 0:
                        p = stack.pop(-1)
                        print(p)
                else:
                        print(-1)

        # 명령3. size
        elif cmd[0] == 'size':
                print(len(stack))

        # 명령4. empty
        elif cmd[0] == 'empty':
                if len(stack) == 0:
                        print(1)
                else:
                        print(0)

        # 명령5. top
        elif cmd[0] == 'top':
                if len(stack) != 0:
                        print(stack[-1])
                else:
                        print(-1)

⏱ 시간 복잡도

1. 각 명령 별 반복 수행 → $O(N)$
2. 명령 (1) push X → $O(C)$
3. 명령 (2) pop→ $O(C)$
4. 명령 (3) size → $O(C)$
5. 명령 (4) empty → $O(C)$
6. 명령 (5) top → $O(C)$

→ 전체 시간복잡도 = O(N)

---

🖍 오답노트

틀린 이유

• 입력을 전부 받은 후에 출력하는 방식으로 코드를 작성함
• import sys

다른 풀이 1. 반복문 내에 조건문 여러개 넣기

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

for _ in range(n):
    cmd = sys.stdin.readline().split()

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

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

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

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

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

다른 풀이 2. 함수 정의

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

def push(x):
    stack.append(x)

def pop():
    if len(stack) == 0:
        print(-1)
    else:
        print(stack.pop())

def size():
    print(len(stack))

def empty():
    if len(stack) != 0:
        print(0)
    else:
        print(1)

def top():
    if len(stack) != 0:
        print(stack[-1])
    else:
        print(-1)

for _ in range(n):
    cmd = sys.stdin.readline().split()

    if cmd[0] == "push":
        push(cmd[1])

    elif cmd[0] == "pop":
        pop()

    elif cmd[0] == "size":
        size()

    elif cmd[0] == "empty":
        empty()

    elif cmd[0] == "top":
        top()

---

정리

깨달은 점

✓ 조건이 여러 개인 경우, ‘조건문을 여러개 사용’하는 것도 좋지만 조건에 맞는 ‘함수를 정의’하고 필요할때 호출하는 것이 더 깔끔하게 느껴졌다.
✓ 여태까지 입력은 input()으로만 사용해왔는데, 이게 시간초과 문제로 이어지는 것을 알지 못했다. 다음 부터는 sys.stdin.readline()을 사용하는 것을 잊지 말아야겠다.

---

References