[Algorithm] BOJ 10828번_스택

03/07/17 on Study

Backjoon Online Judge를 통해 스터디 중인 알고리즘 스터디 모임 과제입니다.
*알고리즘 스터디 모임 : 넥스터즈 8, 9기 개발자 5명으로 구성

사이트

https://www.acmicpc.net/problem/10828

문제

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

명령은 총 다섯 가지이다.

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

입력

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

출력

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

풀이

# Baekjoon Online Judge Q)10828
# Language : python3
# Version : 3.5.2
# Date : 2017. 03. 06
# Junyoung Jung(@sauber92)

import sys

loop = int(input())		# 반복문을 수행할 int형 변수. 첫째 줄에서 입력
stack = []			# 스택 변수
length = len(stack)		# 스택의 길이를 받는 변수

# 첫째 줄에서 입력 받은 수가 (1 ≤ N ≤ 10,000) 을 만족하는지 판별
# 만족을 못하면 프로세스 종료
if loop < 0 or loop > 10000:
    sys.exit()

# 반복문 수행
for i in range(loop):
    # 입력 받는 부분
    # split()을 통해 하나씩 입력 받을 수 있다.
    # Split()이 없으면 loop만큼 입력을 계속 받는다. 
    value = input().split()

    # push 하는 부분
    # value[0]은 입력받은 첫번째 요소이고, value[1]은 두번째 요소이다.
    # 만약 "push 4" 라는 입력을 했다면 value[0] == push, value[1] == 4 이다.
    # python3에서는 append()를 통해 배열에 요소를 추가할 수 있다.
    if value[0] == "push":
        stack.append(int(value[1]))
        length += 1

    elif value[0] == "pop":
        if length == 0:
            print(-1)
        else:
            # python3에서는 배열의 마이너스 인덱싱이 가능하다.
            # "lst[ len(lst) - 1 ]" 에서 "len(lst)" 가 생략되어있다고 생각하면 된다.
            print(stack[-1])
            
            # python3의 함수 중 pop()은 실제 stack의 pop과 같은 역할을 한다.
            # stack의 최상단에 있는 요소를 빼내고 크기를 줄이는 역할
            stack.pop()
            length -= 1

    elif value[0] == "size":
        print(length)


    elif value[0] == "empty":
        if length == 0:
            print(1)
        else:
            print(0)

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

느낀점

같이 넥스터즈를 했던 사람들과 알고리즘 스터디를 시작했다. 매주 백준 온라인 저지에 있는 문제를 주제별로 푸는 스터디인데, 이번주는 Stack과 관련된 문제 3개를 풀기로 하였다.

Stack(스택)은 LIFO(Last In First Out; 후입선출)의 속성을 가진 자료구조이다. Stack은 Queue, Dequeue와 함께 현실 세계를 추상화하는 추상화 자료 구조의 대표적인 예이며 일렬로 늘어선 자료들을 표현한다.

이론적인 내용은 자료구조 수업시간에도 배웠고 C++을 사용하여 구현도 해보았다. 그러나 이번에 하는 스터디에서는 Python을 사용해 보기로 하였기에 Python Wiki와 Docs를 뒤져가면서 문제를 풀었다.

처음엔 런타임에러가 나서 많이 해맸다…그래서 BOJ Slack에 가입을 하고 질문을 하였더니 좋으신 분의 조언으로 코드 수정을 할 수 있었다. 그리고 찾아보니 Python3로 채점하는 것과 Pypy3로 채점하는 것이 수행속도가 다르다는 것을 알게 되었다. Pypy는 JIT(Just In Time)컴파일러로서 CPython보다 빠른 구현을 위해 만들어졌다고 한다.

< 엄청 틀렸다….ㅎ..ㅎㅎㅎ…>

추가

BOJ에 채점현황을 보니 이 문제에서 Pypy3로 제출한 사람은 나를 포함해서 3명이였다. 그런데 나머지 두 분의 코드를 보니 나와는 비교할 수 없을 정도로 짧고 깔끔했으며 수행시간도 짧았다.

n = int(input())

st = []

for i in range(n):
    k = input()
    if k[:3] == 'pus':
        st += [int(k[5:])]
    if k[:3] == 'pop':
        if st==[]: print(-1)
        else: print(st[-1])
        st = st[:-1]
    if k[:3] == 'siz':
        print(len(st))
    if k[:3] == 'emp':
        print(1 if len(st)==0 else 0)
    if k[:3] == 'top':
        if st==[]: print(-1)
        else: print(st[-1])

< 아름답다 >

n=int(input())
data = []
for _ in range(n):
    query = input().split()
    if query[0]=='push':
        data.append(query[1])
    elif query[0]=='pop':
        if len(data) > 0:
            print(data.pop())
        else:
            print(-1)
    elif query[0]=='size':
        print(len(data))
    elif query[0]=='empty':
        print(0 if len(data) > 0 else 1)
    else:
        if len(data) > 0:
            print(data[-1])
        else:
            print(-1)

< 내 코드와 비슷하지만 훨씬 간결하다…bbb >