문제
https://www.acmicpc.net/problem/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
- 깔끔하게 구현한 코드는 위 포스팅에 있다! 이걸 바탕으로 문제를 다시 풀어보면 좋을 것 같다.
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ] 10866. 덱 (0) | 2022.09.07 |
---|---|
[BOJ] 10845. 큐 (0) | 2022.09.07 |
[BOJ] 10816. 숫자카드 2 (0) | 2022.09.07 |
[BOJ] 10814. 나이순 정렬 (0) | 2022.09.07 |
[BOJ] 10250. ACM 호텔 (0) | 2022.09.07 |