백준 10828번(스택)

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

import sys
t = int(sys.stdin.readline())
a = []
for _ in range(t):
    n = sys.stdin.readline().split()
    if n[0] == 'push':
        a.append(n[1])
    elif n[0] == 'pop':
        if len(a) > 0:
            print(a.pop())
        else:
            print(-1)
    elif n[0] == 'size':
        print(len(a))
    elif n[0] == 'empty':
        if len(a) == 0:
            print(1)
        else:
            print(0)
    else:
        if len(a) > 0:
            print(a[-1])
        else:
            print(-1)

Python에서는 리스트가 스택이랑 비슷한 역할을 할수 있어서 리스트를 사용하면 쉽게 구현이 가능한것 같다.

백준 10773번(제로)

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

t = int(input())
a = []
for _ in range(t):
    n = int(input())
    if n != 0:
        a.append(n)
    else:
        a.pop()
print(sum([i for i in a]))

백준 18258번(큐2)

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

import sys
from collections import deque
t = int(sys.stdin.readline())
a = deque([])
for _ in range(t):
    n = sys.stdin.readline().split()
    if n[0] == 'push':
        a.append(n[1])
    elif n[0] == 'pop':
        print(a.popleft()) if len(a) > 0 else print(-1)
    elif n[0] == 'size':
        print(len(a))
    elif n[0] == 'empty':
        print(0) if len(a) > 0 else print(1)
    elif n[0] == 'front':
        print(a[0]) if len(a) > 0 else print(-1)
    else:
        print(a[-1]) if len(a) > 0 else print(-1)

deque

파이썬의 리스트와 같이 요소들을 한 곳에 담아두는 배열이다.
덱(데큐)는 양방향인 queue이다. 양쪽 방향 모두에서 요소를 추가/제거 할수 있다.
그렇기 때문에 리스트보다 데큐가 속도가 훨씬 빠르다. 리스트는 O(n)의 속도, 데큐는 O(1)의 속도 이다.

deque 사용법

from collections import deque

a = deque([])
a.append(1)        # deque([1])
a.appendleft(2)    # deque([2, 1])
a.append(3)        # deque([2, 1, 3])

deque 메서드(list와 비교)

백준 1021번(회전하는 큐)

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

문제를 읽으면서 이해하는데 오랜시간이 걸렸다. 문제를 요약하자면 처음 N개의 원소를 가진 리스트가 주어지는데 그중에서 M개의 숫자를 뽑아서 값이 주어지면 그 값들을 리스트에서 뽑는데 숫자가 이동하는 횟수를 구하는 문제이다.

import sys
from collections import deque

N, M = map(int, input().split())
pick = list(map(int, sys.stdin.readline().split()))
picks = deque([i for i in range(1, N+1)])  # 양방향 queue인 덱을 사용한다.

count = 0
for j in pick:
    while True:
        if j == picks[0]:    # 덱 안에 첫번째 수가 입력값과 똑같은지 확인
            picks.popleft()  # 앞쪽의 수를 빼냄.
            break
        # 입력 값이 덱의 맨처음 수와 다른 수 일시 index()를 사용하여 
        # 입력 값의 위치를 확인한다.
		elif picks.index(j) <= len(picks) / 2:   # index 위치가 왼쪽에 가까울 경우
            picks.rotate(-1)
            count += 1

		elif picks.index(j) > len(picks) / 2:    # index 위치가 오른쪽에 가까울 경우
            picks.rotate()
            count += 1
print(count)

N과 len(picks) 값은 처음에는 같지만 pop()을 사용하면서 값이 달라진다. 처음에는 N 값으로 index위치를 계산하여 시행착호를 격게 되었다.

마치며

오늘은 같은 팀원들과 서로의 코드 리뷰를 해보았다. 같은 문제지만 서로 접근하는 방법이 다르고 코드작성하는 방법도 다달랐다. 다른 사람들은 Java 언어로 알고리즘을 풀어서 솔직히 Java를 배운지도 얼마 안됬지만 요 몇일 언어학습을 하지 않아서 인지 코드를 보는게 어려웠었다. 다시 언어공부에 시간을 투자 해야 될것 같다.