[백준] python 코딩테스트 - 큐(18258, 2164, 3190)
출처 : http://www.yes24.com/Product/Goods/107478270
보통의 취준생을 위한 코딩 테스트 with 파이썬 - YES24
이 책은 손에 잡히는 코딩 테스트 합격 방법을 제시한다. 바로 “백준 플래티넘 5 & 코드 포스 파란색 랭크”로 목표 설정을 구체화한 것이다. 이 수준을 달성하면 웬만한 기업의 코딩 테스트 문
www.yes24.com
* 큐(18258)
▶ 스택과 달리 먼저 삽입된 데이터가 가장 먼저 출력
▶ 배열로도 가능하지 않나? → 배열로 큐의 기능 구현 시 먼저 삽입된 데이터가 삭제될 때마다 Ο(데이터 크기)만큼 소요
//예시 1 2 3 4 5 순서대로 배열 A의 입력에 들어오면 배열 A는?
A[0] = 1, A[1] = 2, A[2] = 3, A[3] = 4, A[4] = 5
//가장 먼저 삽입된 A[0]=1을 지우면?
A[0] = 2, A[1] = 3, A[2] = 4, A[3] = 5
//데이터 삭제할 때 시간복잡도는 O(데이터의 크기)가 되나
//큐를 사용하면 O(1)의 시간 복잡도로 해결할 수 있다https://www.acmicpc.net/problem/18258
18258번: 큐 2
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지
www.acmicpc.net
import sys
from collections import deque # 큐 사용하기 위해 deque 가져옴
n = int(sys.stdin.readline())
queue = deque([])
for i in range(n):
command = sys.stdin.readline().split() # 명령어를 한 줄씩 입력 받음
if command[0] == 'push':
queue.append(command[1])
elif command[0] == 'pop':
if not queue:
print(-1)
else:
print(queue.popleft())
elif command[0] == 'size':
print(len(queue))
elif command[0] == 'empty':
if not queue:
print(1)
else:
print(0)
elif command[0] == 'front':
if not queue:
print(-1)
else:
print(queue[0])
elif command[0] == 'back':
if not queue:
print(-1)
else:
print(queue[-1])
* 카드 2(2164)
▶낮은 번호일수록 위에, 높은 번호일수록 아래에 위치
▶ n =5일 경우
//5 (맨 위)
//4
//3
//2
//1 (맨 아래)
//맨 위의 5가 아닌 맨 아래 1을 삭제(queue.popleft())https://www.acmicpc.net/problem/2164
2164번: 카드2
N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가
www.acmicpc.net
import sys
from collections import deque
N = int(sys.stdin.readline())
queue = deque()
for i in range(N):
queue.append(N-i)
while len(queue) > 1:
queue.pop()
queue.appendleft(queue.pop())
print(queue.popleft())
#queue.popleft() #deque의 전단(맨 위) 삭제
#queue.pop() #deque의 후단(맨 아래) 삭제
#queue.append(데이터) #deque의 후단(맨 아래)에 데이터 삽입
#queue.appendleft(데이터) #deque의 전단(맨 위)에 데이터 삽입
* 뱀(3190)
https://www.acmicpc.net/problem/3190
3190번: 뱀
'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임
www.acmicpc.net
▶ n과 k가 주어지고, 보드의 크기는 n*n, k줄에 사과의 위치가 주어짐
▶ 'ㅣ(L의 소문자)'이 주어지며 'ㅣ'개 줄에 게임 시작 시간 이후에 x 초 뒤에 왼쪽("L") 혹은 오른쪽("D")으로 이동
from collections import deque
def direction_change(d, c):
if c == "L":
d = (d - 1) % 4
else:
d = (d + 1) % 4
return d
N = int(input())
K = int(input())
board = [[0] * N for _ in range(N)]
print("board", board) #[[0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]]
for _ in range(K):
a, b = map(int, input().split())
board[a - 1][b - 1] = 1
L = int(input())
times = {}
for i in range(L):
X, C = input().split()
times[int(X)] = C
dy = [-1, 0, 1, 0] #상하좌우
dx = [0, 1, 0, -1]
direction = 1
time = 1
y, x = 0, 0
snake = deque([[y, x]])
board[y][x] = 2
while True:
y, x = y + dy[direction], x + dx[direction]
if 0 <= y < N and 0 <= x < N and board[y][x] != 2:
if not board[y][x] == 1:
del_y, del_x = snake.popleft()
board[del_y][del_x] = 0
board[y][x] = 2
snake.append([y, x])
if time in times.keys():
direction = direction_change(direction, times[time])
time += 1
else:
break
print(time)