[BOJ] 10828: 스택

이슬비·2022년 3월 21일

boj 스택 자료구조&알고리즘

Algorithm

목록 보기

16/110

일단 지르고 보기... 도대체 몇 번이나 틀린 건지 모르겠다 ^^ 점점 제출하면서 오기가 생겨서 대충 풀고 대충 내기 반복...

어떤 부분에서 틀린 건지 세세히 파헤쳐보자!

10828: 스택

1. 내 풀이: 실패

import sys

N = int(sys.stdin.readline())
stack = []
cnt = 0

while True:
    order = sys.stdin.readline()
    if 'push' in order:
        order_list = order.split()
        stack.append(int(order_list[1]))
    elif 'pop' in order:
        if len(stack)==0:
            print(-1)
        else:
            stack.pop()
    elif 'size' in order:
        print(len(stack))
    elif 'empty' in order:
        if len(stack) == 0:
            print(1)
        else:
            print(0)
    else:
        if len(stack) == 0:
            print(-1)
        else:
            print(stack[-1])
    cnt += 1
    if cnt==N:
        break

문제점이 많아 보이는 나의 풀이... 일단 시간초과가 나지 않게 sys 모듈을 import 한 것은 아주 잘했다 ^^
그런데 for 문을 만들기 귀찮아서 cnt 변수를 따로 설정했었다. 만약 이 코드가 잘 돌아갔어도 cnt가 메모리를 조금 더 차지했지 않았을까... 생각한다. 내 풀이만 보면서 무엇이 잘못되었는지 보는 것보다 맞춘 풀이랑 비교하는 게 더 좋을 것 같다.

2. 내 풀이: 성공

import sys

N = int(sys.stdin.readline())
stack = []

for i in range(N):
   order = sys.stdin.readline().split()
   if order[0] == 'push':
       stack.append(int(order[1]))
   elif order[0] == 'pop':
       if len(stack)==0:
           print(-1)
       else:
           print(stack.pop())
   elif order[0] == 'size':
       print(len(stack))
   elif order[0]=='empty':
       if len(stack) == 0:
           print(1)
       else:
           print(0)
   else:
       if len(stack) == 0:
           print(-1)
       else:
           print(stack[-1])

사실 이건 좀 부끄러운 사실인데 넣고 빼는 정수, 즉 push 뒤에 오는 정수가 당연히 (왜???) 한 자리 수라고 생각해서 처음에는

order = sys.stdin.readline()
    if 'push' in order:
        stack.append(int(order[-1]))

로 썼었다 ㅋㅎ 무식 그 자체... 그러다가 예제 2번을 보고 "오호! 나 바보구나!" 싶어서 리스트로 호다닥 고쳤다.

일단 비교분석을 해보자면

조건문
: 첫 번째에서는 in을 쓰고 두 번째에서는 == 연산자를 썼다. 사실 이 부분으로 인한 문제는 크게 없는 것 같다.
stack.pop() ✨
: 이건 멍청했다기보다는... 그냥 기억이 안났다. 기억이 안 난 것도 아니고 그냥 몰랐음 ^^ pop() 함수를 쓰면 당연히 print도 해주는 줄 알았는데, 그냥 제일 마지막에 들어온 input을 반환해주는 것이었다.

이것들을 제외하고는 크게 다르지 않다...! 도대체 왜 저렇게 도전을 많이 했나... 침착하게 생각하고 풀어보기!

더 알아보기

본격적(?)으로 오늘 실습한 자료구조에 대해서 알아보자!

1. Stack

(출처: https://medium.com/@yms0214/data-structure-stack-%EA%B3%BC-queue-4ac1694b7c27)

오늘 구현한 stack과 push, pop, top에 대해서 아주 잘 설명해놓은 그림이다. Stack 자료구조는 아래가 막힌 그릇(?)이라고 생각하면 된다. 즉, 데이터를 넣으면 다시 데이터를 뺄 때 넣은 순서대로 빠지는 게 아닌, 가장 마지막에 넣어진 데이터가 가장 첫 번째로 빠지게 된다. 이를 FILO (First In Last Out) 이라고 한다.

Stack 자료구조에 데이터를 넣는 행위를 Push, 빼는 행위를 Pop이라고 한다. 이때 가장 위에 있는 데이터를 Top이라고 지칭한다.

이와 유사하면서도 다른 자료구조가 바로 Que이다.