[백준] python 코딩테스트 - 큐(18258, 2164, 3190)

 

 

 

출처 : http://www.yes24.com/Product/Goods/107478270

보통의 취준생을 위한 코딩 테스트 with 파이썬 - YES24

 

 

* 큐(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

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

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번: 뱀

▶ 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)