[BOJ] 10828. 스택

문제

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

10828번: 스택

 

 

 

---

 

주요 아이디어

기본적인 스택 구현 문제이다.

 

---

 

코드 구현 (Python 3)

배열 기반 스택을 구현하고자 했다.

 

# 스택은 전역으로 (매번 전달하기 귀찮)
stack = []

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

def empty():
    if len(stack) < 1:
        print(1)
        return 1
    else:
        print(0)
        return 0

def push(X):

    # 스택 비어있을 경우
    if len(stack) < 1:
        stack.append(X)
        return
    else:
        # 한 칸씩 뒤로 밀고 맨 앞에 추가하기
        stack.append(0)
        for i in range(len(stack)-1, 0, -1):
            stack[i] = stack[i-1]

        stack[0] = X
        return

def pop():
    if len(stack) < 1:
        print(-1)
    else:
        print(stack[0])
        stack.remove(stack[0])
        return

def top():
    if len(stack) < 1:
        print(-1)
        return
    else:
        print(stack[0])
        return stack[0]


N = int(input()) # 명령의 수
t = 0

# 명령 실행
for i in range(N):
    cmd = input().split()
    t = 0

    if cmd[0] == 'push':
        push(int(cmd[1]))
    elif cmd[0] == 'pop':
        pop()
    elif cmd[0] == 'size':
        size()
    elif cmd[0] == 'empty':
        empty()
    elif cmd[0] == 'top':
        top()
    else:
        print('error')
        break

 

 

하지만 시간 초과가 떴다...

---

 

실패 원인

 

top에서만 넣고 뺄 수 있다는 기본 개념을 망각하고 (...) 코드를 짰기 때문이다.

 

이후 코드는 파이썬 기본 메서드를 사용했다.

 

---

 

코드 재구현 (Python 3)

 

N = int(input()) # 명령의 수

# 스택은 전역으로 (매번 전달하기 귀찮)
stack = []
global t
t = -1

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

def empty():
    if len(stack) < 1:
        print(1)
        return 1
    else:
        print(0)
        return 0

# 방향 역순으로 생각할 것
def push(X):
    stack.append(X)
    return

# 1 2 3
def pop():
    if len(stack) < 1:
        print(-1)
    else:
        print(stack[t])
        stack.remove(stack[t])
        return

def top():
    if len(stack) < 1:
        print(-1)
        return
    else:
        print(stack[t])
        return stack[t]


# 명령 실행
for i in range(N):
    cmd = input().split()

    if cmd[0] == 'push':
        push(int(cmd[1]))
        t += 1
    elif cmd[0] == 'pop':
        pop()
        if t > -1:
            t -= 1
    elif cmd[0] == 'size':
        size()
    elif cmd[0] == 'empty':
        empty()
    elif cmd[0] == 'top':
        top()
    else:
        print('error')
        break
    print('stack : ', stack)
    print('t : ', t)

 

 

...

 

왜 틀렸을까?

 

remove method 구현 시, 동일한 원소가 스택에 있을 때 어떻게 remove 되는지 생각하지 않았기 때문!

 

이처럼 동일한 원소 추가 시 예상하지 않았던 앞의 원소가 지워지는 것을 볼 수 있다.

‘remove’ 대신 ‘del’ 키워드 사용

 

 

 

---

코드 재구현 2 (Python 3)

 

import sys

input=sys.stdin.readline


N = int(input()) # 명령의 수

# 스택은 전역으로 (매번 전달하기 귀찮)
stack = []
global t
t = -1

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

def empty():
    if len(stack) < 1:
        print(1)
        return 1
    else:
        print(0)
        return 0

# 방향 역순으로 생각할 것
def push(X):
    stack.append(X)
    return

# 1 2 3
def pop():
    if len(stack) < 1:
        print(-1)
    else:
        print(stack[t])
        del stack[t]
        return

def top():
    if len(stack) < 1:
        print(-1)
        return
    else:
        print(stack[t])
        return stack[t]


# 명령 실행
for i in range(N):
    cmd = input().split()

    if cmd[0] == 'push':
        push(int(cmd[1]))
        t += 1
    elif cmd[0] == 'pop':
        pop()
        if t > -1:
            t -= 1
    elif cmd[0] == 'size':
        size()
    elif cmd[0] == 'empty':
        empty()
    elif cmd[0] == 'top':
        top()
    else:
        print('error')
        break

 

 

 

---

 

제출 결과

 

 

 

---

 

코드 개선 방안

• 사실 스택 개념을 복습하기 전에 짠 코드라 엉성한 부분이 많이 보인다ㅠㅠ
• https://ll2ll.tistory.com/9

[자료구조] 06. 스택 (Stack)

 

• 깔끔하게 구현한 코드는 위 포스팅에 있다! 이걸 바탕으로 문제를 다시 풀어보면 좋을 것 같다.