출처: [백준] 13417번 카드 문자열

문제

N장의 카드가 일렬로 놓여있다. 각 카드에는 알파벳이 하나씩 적혀있다. 태욱이는 가장 왼쪽에 있는 카드부터 차례대로 한 장씩 가져올 수 있다. 가장 처음에 가져온 카드는 자신의 앞에 놓는다. 그다음부터는 가져온 카드를 자신의 앞에 놓인 카드들의 가장 왼쪽, 또는 가장 오른쪽에 놓는다. 태욱이는 모든 카드를 다 가져온 후에 자신의 앞에 놓인 카드를 순서대로 이어 붙여 카드 문자열을 만들려고 한다.

예를 들어 3장의 카드가 [M, K, U] 순으로 놓여있다고 하자. 태욱이는 먼저 가장 왼쪽에 있는 “M”이 적힌 카드를 가져와서 자신의 앞에 놓는다. 다음으로 남은 카드 중 가장 왼쪽에 있는 “K”가 적힌 카드를 가져와서 가장 왼쪽에 두고, 이어서 “U”가 적힌 카드를 가져와서 다시 가장 왼쪽에 두면 “UKM”이라는 문자열을 만들 수 있다. 만약 “K”가 적힌 카드를 가져와서 가장 왼쪽에 두고, 이어서 “U”가 적힌 카드를 가져와서 가장 오른쪽에 두면 “KMU”라는 문자열을 만들 수 있다. 이때, 태욱이가 만들 수 있는 문자열 중 사전 순으로 가장 빠른 문자열은 “KMU”이다.

N장의 카드에 적혀있는 알파벳의 처음 순서가 주어질 때, 태욱이가 만들 수 있는 카드 문자열 중 사전 순으로 가장 빠른 문자열을 출력하는 프로그램을 작성하시오.

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각각의 테스트 케이스의 첫째 줄에 처음에 놓여있는 카드의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 두 번째 줄에는 N장의 카드에 적힌 알파벳의 초기 순서가 주어진다. 가장 왼쪽에 있는 카드에 적혀있는 알파벳부터 순서대로 N개가 공백으로 구분되어 주어진다. 모든 카드에는 한 개씩의 알파벳이 적혀있으며, 모두 대문자이다.

출력

출력은 표준 출력을 사용한다. 입력받은 데이터에 대해, 한 줄에 1개씩 태욱이가 만들 수 있는 문자열 중에서 사전 순으로 가장 빠른 문자열을 출력한다.

예제 입력 1

1
2
3
4
5
6
7

3
3
M K U
5
A S D F G
7
B A C A B A C

예제 출력 1

1
2
3

KMU
ASDFG
AAABCBC

출처

• University > 국민대학교 > 2016 국민대학교 교내 경시대회 E번
  • 문제를 만든 사람: game2k

알고리즘 분류

• 자료 구조
• 문자열
• 그리디 알고리즘
• 덱

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

import sys
from collections import deque

input = sys.stdin.readline

T = int(input())
for _ in range(T):
    N = int(input())
    card_list = deque(input().rstrip().split())
    new_list = deque(card_list.popleft())

    while card_list:
        temp = card_list.popleft()
        if temp > new_list[0]:
            new_list.append(temp)
        else:
            new_list.appendleft(temp)

    print(''.join(new_list))

출처: [백준] 18115번 카드 놓기

문제

수현이는 카드 기술을 연습하고 있다. 수현이의 손에 들린 카드를 하나씩 내려놓아 바닥에 쌓으려고 한다. 수현이가 쓸 수 있는 기술은 다음 3가지다.

1. 제일 위의 카드 1장을 바닥에 내려놓는다.
2. 위에서 두 번째 카드를 바닥에 내려놓는다. 카드가 2장 이상일 때만 쓸 수 있다.
3. 제일 밑에 있는 카드를 바닥에 내려놓는다. 카드가 2장 이상일 때만 쓸 수 있다.

수현이는 처음에 카드 N장을 들고 있다. 카드에는 1부터 N까지의 정수가 중복되지 않게 적혀 있다. 기술을 N번 사용하여 카드를 다 내려놓았을 때, 놓여 있는 카드들을 확인했더니 위에서부터 순서대로 1, 2, …, N이 적혀 있었다!

놀란 수현이는 처음에 카드가 어떻게 배치되어 있었는지 궁금해졌다. 처음 카드의 상태를 출력하여라.

입력

첫 번째 줄에는 N (1 ≤ N ≤ 106)이 주어진다.

두 번째 줄에는 길이가 N인 수열 A가 주어진다. Ai가 x이면, i번째로 카드를 내려놓을 때 x번 기술을 썼다는 뜻이다. Ai는 1, 2, 3 중 하나이며, An은 항상 1이다.

출력

초기 카드의 상태를 위에서부터 순서대로 출력하여라.

예제 입력 1

1
2

5
1 1 1 1 1

예제 출력 1

1

5 4 3 2 1

예제 입력 2

1
2

5
2 3 3 2 1

예제 출력 2

1

1 5 2 3 4

출처

• University > 서강대학교 > 2019 Sogang Programming Contest (Champion) C번
  • 문제를 검수한 사람: jh05013, shiftpsh
  • 문제를 만든 사람: semteo04

알고리즘 분류

• 자료 구조
• 덱

풀이

1
2
3
4

반대로
1) 맨위의 카드를 바닥으로
2) 맨위의 카드를 바닥에서 2번째로
3) 맨위의 카드를 맨위로

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
card_list = deque(range(1, N + 1))
commands = list(map(int, input().split()))
init_list = deque()

while commands:
    command = commands.pop()
    temp = card_list.popleft()
    if command == 1:
        init_list.appendleft(temp)
    elif command == 2:
        init_list.insert(1, temp)
    elif command == 3:
        init_list.append(temp)

print(*init_list)

출처: [백준] 20301번 반전 요세푸스

문제

요세푸스 문제는 다음과 같다.

1번 사람 오른쪽에는 2번 사람이 앉아 있고, 2번 사람 오른쪽에는 3번 사람이 앉아 있고, 계속하여 같은 방식으로 N명의 사람들이 원을 이루며 앉아 있다. N번 사람 오른쪽에는 1번 사람이 앉아 있다. 이제 K(≤N)번 사람을 우선 제거하고, 이후 직전 제거된 사람의 오른쪽의 K번째 사람을 계속 제거해 나간다. 모든 사람이 제거되었을 때, 제거된 사람의 순서는 어떻게 될까?

이 문제의 답을 (N, K)–요세푸스 순열이라고 하며, (7, 3)–요세푸스 순열은 ⟨3,6,2,7,5,1,4⟩가 된다.

하지만 한 방향으로만 계속 돌아가는 건 너무 지루하다. 따라서 요세푸스 문제에 재미를 더하기 위해 M명의 사람이 제거될 때마다 원을 돌리는 방향을 계속해서 바꾸려고 한다. 이렇게 정의된 새로운 문제의 답을 (N, K, M)–반전 요세푸스 순열이라고 하며, (7, 3, 4)–반전 요세푸스 순열은 ⟨3,6,2,7,1,5,4⟩가 된다.

N, K, M이 주어질 때, (N, K, M)–반전 요세푸스 순열을 계산해 보자.

입력

첫째 줄에 정수 N, K, M이 주어진다. (1≤N≤5 000, 1≤K,M≤N)

출력

(N, K, M)–반전 요세푸스 순열을 이루는 수들을 한 줄에 하나씩 순서대로 출력한다.

예제 입력 1

1

7 3 4

예제 출력 1

1
2
3
4
5
6
7

3
6
2
7
1
5
4

출처

• University > 서강대학교 > 2020 Sogang Programming Contest (Master) C번
  • 문제를 검수한 사람: gumgood, jhnah917, pichulia, QuqqU, rhs0266, shiftpsh, sogangcse, woonikim
  • 문제를 만든 사람: sbrus_1213

알고리즘 분류

• 구현
• 자료 구조
• 시뮬레이션
• 덱

소스코드 (최초)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

import sys
from collections import deque

input = sys.stdin.readline

N, K, M = map(int, input().split())

people = deque(x for x in range(1, N + 1))

count = 0
direction = 1
while people:
    if direction:  # 오른쪽
        for _ in range(K - 1):
            people.append(people[0])
            people.popleft()
    elif not direction:  # 왼쪽
        for _ in range(K):
            people.appendleft(people.pop())

    print(people.popleft())
    count += 1
    if count == M:
        count = 0
        direction = not direction

소스코드 (수정)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

import sys
from collections import deque

input = sys.stdin.readline

N, K, M = map(int, input().split())

people = deque(x for x in range(1, N + 1))

while people:
    for _ in range(M):
        people.rotate(-(K - 1))  # 오른쪽
        if not people:
            break
        print(people.popleft())

    for _ in range(M):
        people.rotate(K)  # 왼쪽
        if not people:
            break
        print(people.popleft())

출처: [백준] 2346번 풍선 터뜨리기

문제

1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선이 있다. 각 풍선 안에는 종이가 하나 들어있고, 종이에는 -N보다 크거나 같고, N보다 작거나 같은 정수가 하나 적혀있다. 이 풍선들을 다음과 같은 규칙으로 터뜨린다.

우선, 제일 처음에는 1번 풍선을 터뜨린다. 다음에는 풍선 안에 있는 종이를 꺼내어 그 종이에 적혀있는 값만큼 이동하여 다음 풍선을 터뜨린다. 양수가 적혀 있을 경우에는 오른쪽으로, 음수가 적혀 있을 때는 왼쪽으로 이동한다. 이동할 때에는 이미 터진 풍선은 빼고 이동한다.

예를 들어 다섯 개의 풍선 안에 차례로 3, 2, 1, -3, -1이 적혀 있었다고 하자. 이 경우 3이 적혀 있는 1번 풍선, -3이 적혀 있는 4번 풍선, -1이 적혀 있는 5번 풍선, 1이 적혀 있는 3번 풍선, 2가 적혀 있는 2번 풍선의 순서대로 터지게 된다.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000)이 주어진다. 다음 줄에는 차례로 각 풍선 안의 종이에 적혀 있는 수가 주어진다. 종이에 0은 적혀있지 않다.

출력

첫째 줄에 터진 풍선의 번호를 차례로 나열한다.

예제 입력 1

1
2

5
3 2 1 -3 -1

예제 출력 1

1

1 4 5 3 2

출처

• 잘못된 데이터를 찾은 사람: tncks0121

알고리즘 분류

• 자료 구조
• 덱

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

import sys
from collections import deque

input = sys.stdin.readline

N = int(input())

balloons = [x for x in range(1, N + 1)]
papers = list(map(int, input().split()))

bomb = deque()
for balloon, paper in zip(balloons, papers):
    bomb.append([balloon, paper])

while bomb:
    balloon, paper = bomb.popleft()
    print(balloon, end=" ")
    if bomb:
        if paper > 0:
            for _ in range(paper - 1):
                bomb.append(bomb.popleft())
        else:
            for _ in range(-paper):
                bomb.appendleft(bomb.pop())

출처: [백준] 5464번 주차장

문제

시내 주차장은 1부터 N까지 번호가 매겨진 N개의 주차 공간을 가지고 있다. 이 주차장은 매일 아침 모든 주차 공간이 비어 있는 상태에서 영업을 시작하며, 하룻동안 다음과 같은 방식으로 운영된다. 차가 주차장에 도착하면, 주차장 관리인이 비어있는 주차 공간이 있는지를 검사한다. 만일 비어있는 공간이 없으면, 차량을 빈 공간이 생길 때까지 입구에서 기다리게 한다. 만일 빈 주차 공간이 하나만 있거나 또는 빈 주차 공간이 없다가 한 대의 차량이 주차장을 떠나면 곧바로 그 장소에 주차를 하게 한다. 만일 빈 주차 공간이 여러 곳이 있으면, 그 중 번호가 가장 작은 주차 공간에 주차하도록 한다. 만일 주차장에 여러 대의 차량이 도착하면, 일단 도착한 순서대로 입구의 대기장소에서 줄을 서서 기다려야 한다. 대기장소는 큐(queue)와 같이, 먼저 대기한 차량부터 주차한다.

주차료는 주차한 시간이 아닌 차량의 무게에 비례하는 방식으로 책정된다. 주차료는 차랑의 무게에다 주차 공간마다 따로 책정된 단위 무게당 요금을 곱한 가격이다.

주차장 관리원은 오늘 M대의 차량이 주차장을 이용할 것이라는 것을 알고 있다. 또한, 차량들이 들어오고 나가는 순서도 알고 있다.

주차 공간별 요금과 차량들의 무게와 출입 순서가 주어질 때, 오늘 하룻동안 주차장이 벌어들일 총 수입을 계산하는 프로그램을 작성하라.

입력

반드시 표준 입력으로부터 다음의 데이터를 읽어야 한다.

• 첫 번째 줄에는 정수 N과 M이 빈칸을 사이에 두고 주어진다.

• 그 다음 N개의 줄에는 주차 공간들의 단위 무게당 요금을 나타내는 정수들이 주어진다. 그 중 s번째 줄에는 주차 공간 s의 단위 무게당 요금 Rs가 들어있다.

• 그 다음 M개의 줄에는 차량들의 무게를 나타내는 정수들이 주어진다. 차량들은 1 부터 M 까지 번호로 구분되고, 이 번호는 출입 순서와는 상관없다. 이 M개의 줄 중 k번째 줄에는 차량 k의 무게를 나타내는 정수 Wk가 들어있다.

• 그 다음 2*M 개의 줄에는 차량들의 주차장 출입 순서를 나타내는 정수들이 한 줄에 하나씩 주어진다. 양의 정수 i는 차량 i가 주차장에 들어오는 것을 의미하고, 음의 정수 -i는 차량 i가 주차장에서 나가는 것을 의미한다. 주차장에 들어오지 않은 차량이 주차장에서 나가는 경우는 없다. 1 번부터 M 번까지 모든 차량은 정확하게 한 번씩 주차장에 들어오고, 한 번씩 주차장에서 나간다. 또한 입구에서 대기 중인 차량이 주차를 하지 못하고 나가는 경우는 없다.

• 1 ≤ N ≤ 100 주차 공간의 수

• 1 ≤ M ≤ 2,000 차량의 수

• 1 ≤ Rs ≤ 100 주차 공간 s의 단위 무게당 요금

• 1 ≤ Wk ≤ 10,000 차량 k의 무게

출력

출력은 반드시 표준 출력으로 하여야 하며, 하나의 줄에 한 개의 정수를 출력한다. 이 정수는 오늘 하룻동안 주차장이 벌어들인 총 수입이다.

예제 입력 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3 4
2
3
5
200
100
300
800
3
2
-3
1
4
-4
-2
-1

예제 출력 1

1

5300

예제 입력 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2 4
5
2
100
500
1000
2000
3
1
2
4
-1
-3
-2
-4

예제 출력 2

1

16200

힌트

• 차량 3이 주차 공간 1에 주차한다. 주차료는 300 * 2 = 600 이다.
• 차량 2가 주차 공간 2에 주차한다. 주차료는 100 * 3 = 300 이다.
• 차량 1이 차랑 3이 떠난 주차공간 1에 주차한다. 주차료는 200 * 2 = 400 이다.
• 차량 4가 마지막 남은 주차 공간 3에 주차한다. 주차료는 800 * 5 = 4,000 이다.

출처

• Olympiad > International Olympiad in Informatics > IOI 2009 5번

알고리즘 분류

• 구현
• 자료 구조
• 시뮬레이션
• 큐

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

import sys
from collections import deque
import heapq

input = sys.stdin.readline

N, M = map(int, input().split())
# N~: 단위 무게당 요금을 나타내는 정수, N: 주차공간 1,2,3....
# M~: 차량들의 무게


fees = [int(input()) for _ in range(N)]
weights = [int(input()) for _ in range(M)]

parking = {}
for i in range(M + 1):
    parking[i + 1] = []

waiting = deque()
total_fee = 0

parking_idx = [x for x in range(N)]
heapq.heapify(parking_idx)

for i in range(2 * M):
    if parking_idx and waiting:
        car_num = waiting.popleft()
        idx = heapq.heappop(parking_idx)
        parking[car_num] = [idx, fees[idx], weights[car_num - 1]]

    car_num = int(input())
    if car_num > 0:  # 입차
        if parking_idx:
            idx = heapq.heappop(parking_idx)
            parking[car_num] = [idx, fees[idx], weights[car_num - 1]]
        else:
            waiting.append(car_num)

    else:
        car_num = abs(car_num)
        idx = parking[car_num][0]
        fee = parking[car_num][1]
        weight = parking[car_num][2]
        total_fee += fee * weight
        heapq.heappush(parking_idx, idx)

print(total_fee)

출처: [백준] 3190번 뱀

문제

‘Dummy’ 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.

게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.

뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.

• 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
• 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
• 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.

입력

첫째 줄에 보드의 크기 N이 주어진다. (2 ≤ N ≤ 100) 다음 줄에 사과의 개수 K가 주어진다. (0 ≤ K ≤ 100)

다음 K개의 줄에는 사과의 위치가 주어지는데, 첫 번째 정수는 행, 두 번째 정수는 열 위치를 의미한다. 사과의 위치는 모두 다르며, 맨 위 맨 좌측 (1행 1열) 에는 사과가 없다.

다음 줄에는 뱀의 방향 변환 횟수 L 이 주어진다. (1 ≤ L ≤ 100)

다음 L개의 줄에는 뱀의 방향 변환 정보가 주어지는데, 정수 X와 문자 C로 이루어져 있으며. 게임 시작 시간으로부터 X초가 끝난 뒤에 왼쪽(C가 ‘L’) 또는 오른쪽(C가 ‘D’)로 90도 방향을 회전시킨다는 뜻이다. X는 10,000 이하의 양의 정수이며, 방향 전환 정보는 X가 증가하는 순으로 주어진다.

출력

첫째 줄에 게임이 몇 초에 끝나는지 출력한다.

예제 입력 1

1
2
3
4
5
6
7
8
9

6
3
3 4
2 5
5 3
3
3 D
15 L
17 D

예제 출력 1

1

9

예제 입력 2

1
2
3
4
5
6
7
8
9
10
11

10
4
1 2
1 3
1 4
1 5
4
8 D
10 D
11 D
13 L

예제 출력 2

1

21

예제 입력 3

1
2
3
4
5
6
7
8
9
10
11
12

10
5
1 5
1 3
1 2
1 6
1 7
4
8 D
10 D
11 D
13 L

예제 출력 3

1

13

출처

• Olympiad > Croatian Highschool Competitions in Informatics > 2005 > National Competition #1 - Juniors 2번
  • 문제의 오타를 찾은 사람: dlwocks31, hax3
  • 빠진 조건을 찾은 사람: doju, joonas, zhsks311
  • 문제를 번역한 사람: sehun

알고리즘 분류

• 구현
• 자료 구조
• 시뮬레이션
• 덱
• 큐

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
board = [[0] * (N) for _ in range(N)]  # NxN 보드 생성

K = int(input())  # 사과 개수
for _ in range(K):  # 사과 위치 지정 0:없음, 1:있음
    y, x = map(int, input().split())
    board[y - 1][x - 1] = 2

# 우, 하, 좌, 상 // 시계방향
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

L = int(input())  # 방향 전환 횟수
times = deque()
directions = deque()
for _ in range(L):
    time, dire = input().rstrip().split()
    times.append(int(time))
    directions.append(dire)

count = 0
direction = 0
nx, ny = 0, 0  # 초기위치
visited = deque([[ny, nx]])

while True:
    count += 1
    # 칸 이동
    nx += dx[direction]
    ny += dy[direction]
    if 0 <= nx < N and 0 <= ny < N and board[ny][nx] != 1:  # 보드 체크
        # 사과가 있으면 그냥 추가, 없으면 꼬리 제거하고 추가
        if board[ny][nx] == 0:  # 사과가 없으면
            temp_y, temp_x = visited.popleft()
            board[temp_y][temp_x] = 0  # 꼬리 줄어듬
        board[ny][nx] = 1
        visited.append([ny, nx])

    else:
        print(count)
        exit(0)

    if count in times:
        dire = directions.popleft()
        if dire == 'D':
            direction += 1
            if direction > 3:
                direction = 0
        else:
            direction -= 1
            if direction < 0:
                direction = 3

출처: [백준] 11116번 교통량

문제

승민이는 마포대교의 교통량이 얼마인지를 측정하고있다. 승민이는 도로 맞은 편을 잇는 두개의 끈을 일정 간격 사이로 매달아 놓았다. 그리고 자동차가 끈위로 지나갈때 끈 끝에 있는 작은 박스에는 그 때 의 시간이 기록된다.

예를 들어, 자동차가 왼쪽에서 올 때 네 번의 기록을 얻게 된다.

• 왼쪽 줄 위로 앞 바퀴가 지나 간 시간 t
• 왼쪽 줄 위로 뒷 바퀴가 지나 간 시간 t + 500
• 오른쪽 줄 위로 앞 바퀴가 지나 간 시간 t + 1000
• 오른쪽 줄 위로 뒷 바퀴가 지나 간 시간 t + 1500

자동차가 오른쪽에서 올 때도 같은 규칙으로 오른쪽과 왼쪽을 바꾸어 측정하면 된다. 주어진 두개의 시간 기록으로 왼쪽에서 얼마나 많은 차가 왔는지 알아내면 된다. 한 끈 위에는 많아야 한 대의 차량이 지나가고 있다.

입력

첫 번째 줄에 n (1 ≤ n ≤ 100) 까지의 테스트 케이스의 개수를 입력 한다. 각각의 테스트 케이스에는 박스에서 측정 된 시간 기록의 개수 m (m ≤ 200)을 입력한다. 다음 줄에는 왼쪽 박스에서 측정된 109 보다 작은 시간 기록 m개를 입력한다. 그 다음 줄에는 오른쪽 박스에서 측정된 109 보다 작은 시간 기록 m개를 입력한다.

출력

각각의 테스트케이스에 대해 왼쪽에서 오는 차의 숫자를 출력한다.

예제 입력 1

1
2
3
4
5
6
7

2
4
17 517 1432 1932
432 932 1017 1517
6
235 451 735 951 2351 2851
1235 1351 1451 1735 1851 1951

예제 출력 1

1
2

1
2

힌트

예제의 첫 번째 테스트 케이스인 Case #1은 문제에서 예로들어서 설명한 세 개의 물품에 대한 정상가격과 할인가격 6개입니다. 또한 예제의 Case #2에서는 여러 품목이 동일한 가격을 가질 수 있고, 어떤 품목의 할인가격이 다른 품목 정상가격과 같을 수도 있습니다.

출처

• Contest > IDI Open Contest > IDI Open 2008 I번
  • 문제를 번역한 사람: tols91

알고리즘 분류

• 구현
• 자료 구조
• 큐

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

import sys
from collections import deque

input = sys.stdin.readline

N = int(input())

for _ in range(N):
    M = int(input())
    left_box = deque(map(int, input().split()))
    right_box = deque(map(int, input().split()))

    car_count = 0
    count = 0
    while left_box:
        temp = left_box.popleft()
        if temp + 1000 in right_box:
            count += 1
        if count == 2:
            count = 0
            car_count += 1

    print(car_count)

출처: [백준] 12034번 김인천씨의 식료품가게 (Large)

문제

전설적인 인천 식료품가게의 주인인 김인천 씨는 대대적인 할인행사를 계획하고 있습니다. 계산을 단순하게하기 위해 그는 25% 할인된 가격으로 상점의 모든 품목을 판매하기로 결정했습니다. 즉, 각 품목의 판매 가격은 정상 가격의 정확히 75 %입니다. 우연하게도 인천 식료품가게에서 판매하는 모든 물건의 정상가는 4의 배수인 정수이고, 할인된 가격 역시 편리하게도 모두 정수입니다.

김인천씨는 이 할인행사를 준비하기위해서 먼저 모든 판매물품의 할인된 판매가격을 프린터로 출력을 실행했고, 또한 할인행사 종료후 다시 쓸 모든 품목에 정상가격표 역시 출력을 실행하였습니다.

손님이 찾아와 잠깐 자리를 비웠던 김인천씨가 다시 가격표의 출력을 확인하기 위해서 프린터로 돌아와보니, 공교롭게 프린터는 모든 물품의 할인가격과 정상가격을 따로 구분하지 않고 오름차순으로 정렬한 뒤 순서대로 출력하여 하나의 출력물 더미를 만들었습니다. 각 품목의 할인가격표와 정상가격표 모두가 출력물 더미의 어딘가에 있습니다. 그러나 두 유형(할인가격, 정상가격)의 가격표는 비슷하게 보이고, 모든 품목의 가격을 기억하지 못하기 때문에 김인천씨는 어느 가격표가 할인가격표인지 확신할 수 없습니다. 이 상황에서 김인천씨는 무엇이 할인가격표인지 구분해낼 수 있을까요?

예를 들어, 정상가격이 20, 80, 100 인 경우 할인가격은 15, 60, 75이며 프린터의 인쇄출력더미는 오름차순으로 정렬된 15, 20, 60, 75, 80, 100 가격표들로 구성됩니다.

입력

입력의 첫 번째 라인(줄)은 테스트 사례의 케이스의 수 T를 나타냅니다. 이후의 라인은 T개의 테스트 케이스가 이어집니다. 각 테스트 케이스는 두 줄로 구성됩니다. 첫 번째 줄에는 INU 식료품가게에 존재하는 상품수인 단일 정수 N이 포함됩니다. 두 번째 줄에는 프린터에서 가격의 오름차순으로 인쇄한 2N개의 정수 P1, P2, …, P2N이 주어집니다.

입력값의 제한은 아래와 같습니다

• 1 ≤ T ≤ 100.
• 모든 i에 대해서 1 ≤ Pi ≤ 109.
• 모든 i에 대해서 Pi ≤ Pi+1. (가격은 오름차순으로 존재)
• 정답은 단 하나만 존재하는것이 보장되어 있음.
• 1 ≤ N ≤ 100

출력

개별 테스트 케이스에 대해서 출력라인은 “Case #x: y” 형식(큰 따옴표는 제외)으로 출력하며, x는 1부터 시작하는 테스트 케이스의 번호 (인덱스)이며, y는 할인가격에 해당하는 오름차순으로 정렬된 N개의 정수들이다.

예제 입력 1

1
2
3
4
5

2
3
15 20 60 75 80 100
4
9 9 12 12 12 15 16 20

예제 출력 1

1
2

Case #1: 15 60 75
Case #2: 9 9 12 15

힌트

예제의 첫 번째 테스트 케이스인 Case #1은 문제에서 예로들어서 설명한 세 개의 물품에 대한 정상가격과 할인가격 6개입니다. 또한 예제의 Case #2에서는 여러 품목이 동일한 가격을 가질 수 있고, 어떤 품목의 할인가격이 다른 품목 정상가격과 같을 수도 있습니다.

출처

• Contest > Google Code Jam > Code Jam to I/O 2016 for Women > Code Jam A2번

알고리즘 분류

• 구현
• 자료 구조
• 큐

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

import sys

input = sys.stdin.readline

T = int(input())

for t in range(T):
    N = int(input())
    price_list = sorted(map(int, input().split()), reverse=True)
    dc_list = []

    while price_list:
        price = price_list.pop()

        if price * 100 // 75 in price_list:
            dc_list.append(price)
            price_list.remove(price * 100 // 75)

    print("Case #{0}: ".format(t + 1), end="")
    print(*dc_list)

출처: [백준] 17952번 과제는 끝나지 않아!

문제

인터넷을 사용하기 위해서는 컴퓨터에 인터넷 회선을 연결하거나 Wi-Fi를 연결해야 한다. 이렇게 연결된 네트워크를 통해 컴퓨터에는 통신이 가능하다. 마음에 드는 노래나 동영상이 있는 곳에 파일을 전송해달라는 요청을 보내고 파일을 받는 식으로 말이다.

우리가 보낸 요청은 어떻게 목적지까지 도달하는 것일까? 컴퓨터에서는 패킷이라고 하는 형태로 정보를 주고 받는다. 네트워크의 유저들은 1:1로 연결되어 있지 않으므로, 일반적으로 패킷은 라우터라는 장비를 여러 번 거친다. 그러면 라우터에서는 패킷을 다른 라우터로 보내거나, 만약 목적지와 직접적으로 연결되어 있다면 그곳으로 보낼 수도 있다. 즉, 택배 회사의 물류 센터와 비슷한 역할을 한다고 보면 된다.

그림1. 네트워크에 존재하는 라우터들의 구성 예시

라우터 내부를 들여다보면 처리해야 할 패킷을 임시적으로 보관하기 위한 버퍼가 존재한다. 이 버퍼에는 라우터에 입력으로 들어온 패킷들이 순서대로 위치하고, 라우터에서는 먼저 온 패킷부터 하나씩 처리한 후 버퍼에서 제거한다. 만약 라우터가 패킷을 처리하는 속도보다 패킷이 들어오는 속도가 더 빠를경우 버퍼가 꽉 차거나 넘쳐버릴 것이다. 그렇게 되면 버퍼에 공간이 생길 때까지 입력받는 패킷은 모두 버려진다.

통신의 원리를 배웠으니까 간단하게 라우터의 작동 원리를 구현해보자. 물론 하나의 라우터만 존재한다고 가정하며, 우리가 다룰 부분은 라우터의 입출력이 주어졌을 때 버퍼의 상태가 어떻게 변하는가이다. 그러니까 라우터가 패킷을 구체적으로 어떤 방식으로 처리하고, 어디로 보내고 이런 것들은 생각하지 말자.

입력

첫 줄에는 라우터 내부에 존재하는 버퍼의 크기를 나타내는 자연수 N이 주어진다.

둘째 줄부터 한 줄에 하나씩 라우터가 처리해야 할 정보가 주어진다. 모든 정보는 발생한 시간순으로 주어졌다고 가정한다. 양의 정수는 해당하는 번호의 패킷이 입력으로 들어왔다는 것을 의미하고, 0은 라우터가 패킷 하나를 처리했다는 것을 의미한다. 이때, 버퍼가 비어있을때는 0이 입력으로 들어오지 않는다. -1은 입력의 끝을 나타낸다.

출력

라우터에 남아있는 패킷을 앞에서부터 순서대로 공백으로 구분해서 출력하면 된다. 만약 비어있을 경우 empty라고 출력한다.

Small (50점)

• 1 ≤ N ≤ 100,000
• 라우터가 처리해야 할 정보의 수는 N보다 작거나 같다.

Large(50점)

• 1 ≤ N ≤ 100,000
• 1 ≤ N ≤ 100,000

예제 입력 1

1
2
3
4
5
6
7
8
9
10
11
12

5
1
2
0
3
4
0
5
6
0
0
-1

예제 출력 1

1

5 6

예제 입력 2

1
2
3
4
5
6
7
8
9

1
1
2
3
4
5
6
7
-1

예제 출력 2

1

1

예제 입력 3

1
2
3
4
5
6
7
8
9
10
11
12
13

1
1
2
0
3
4
0
5
6
0
7
0
-1

예제 출력 3

1

empty

출처

• University > 아주대학교 > 2018 Ajou Programming Contest: Division 2 B번
  • 문제를 만든 사람: luke0201

알고리즘 분류

• 자료 구조
• 큐

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
buffer = deque()
full = 0
while True:
    packet = int(input())

    if packet == -1:
        break
    elif packet == 0:
        buffer.popleft()
        full -= 1
    else:
        if full >= N:
            continue
        else:
            buffer.append(packet)
            full += 1

if buffer:
    print(*buffer)
else:
    print("empty")

출처: [백준] 17225번 세훈이의 선물가게

문제

세훈이는 선물가게를 운영한다. 세훈이의 선물가게는 특이하게도 손님이 어떤 선물을 구매할지 선택할 수가 없다. 대신 세훈이의 취향으로 랜덤하게 준비된 선물 중 몇 개를 구매할 것인지, 파란색과 빨간색 중 어떤 색으로 포장 받을 것인지만 결정해 주문할 수 있다.

상민이와 지수는 세훈이의 가게에서 선물 포장을 맡은 아르바이트생이다. 손님들은 파란색 포장지를 원하면 상민이에게, 빨간색 포장지를 원하면 지수에게 주문을 한다. 두 사람은 각자 주문을 받으면 그때부터 포장을 시작하는데, 현재 남아있는 선물 중 가장 앞에 있는 선물을 가져와 포장하고 주문을 받은 개수만큼 이를 반복하는 형태다. 이때 선물 하나를 포장하는 데 상민이는 A초, 지수는 B초가 걸린다. 두 사람 모두 받거나 밀린 주문이 없는데 미리 선물을 가져오거나 포장하는 일은 없으며, 두 사람이 동시에 선물을 가져올 때는 알바짬이 조금 더 있는 상민이가 먼저 가져오고, 지수가 그 뒤의 선물을 가져온다.

세훈이는 어제 구매한 선물이 망가져 있다는 항의 전화를 받았다. 자신이 준비한 선물에는 문제가 없었기에 손님에게 포장지의 색을 물었지만, 손님은 자신이 받은 선물이 무엇인지만 말하며 화를 낼 뿐이었다. 어쩔 수 없이 세훈이는 어제 가게를 방문한 손님들의 주문 내역을 보고 그 선물을 누가 포장했는지 파악하려 한다.

방문한 손님의 수와 각 손님이 주문한 시각, 선택한 포장지, 포장 받을 선물의 개수가 주어졌을 때 상민이와 지수가 각자 어떤 선물들을 포장했는지 알아내는 프로그램을 작성해보자.

입력

첫 줄에 상민이가 선물 하나를 포장하는 데 걸리는 시간 A, 지수가 선물 하나를 포장하는 데 걸리는 시간 B, 어제 세훈이 가게의 손님 수 N(1 ≤ N ≤ 1,000)이 주어진다.

이후 N개의 줄에 걸쳐 1번부터 N번 손님의 주문 시각 ti(1 ≤ ti ≤ 86,400), 선택한 포장지의 색깔 ci(ci = “B”|”R”), 주문한 선물의 개수 mi(1 ≤ mi ≤ 100)가 주어진다.

ti는 가게가 오픈한 지 ti초 후에 손님이 주문했음을 뜻하며 ci는 포장지의 색깔을 의미하는 알파벳으로 “B”는 파란색을, “R”은 빨간색을 의미한다. 주어지는 입력은 시간의 흐름에 맞게 ti의 오름차순으로 주어지며, 서로 같은 시간에 주문한 손님은 없다.

출력

첫 번째 줄에 상민이가 포장한 선물의 개수를 출력한다. 이후 두 번째 줄에 상민이가 포장한 선물들의 번호를 오름차순으로 공백으로 구분하여 출력한다.

세 번째 줄에 지수가 포장한 선물의 개수를 출력한다. 이후 네 번째 줄에 지수가 포장한 선물들의 번호를 오름차순으로 공백으로 구분하여 출력한다.

서브태스크 1 (100점)

• A = B = 0

A, B가 0이라는 것은 해당 아르바이트생의 포장 속도가 너무 빨라서, 주문과 동시에 해당 주문의 모든 선물 포장이 끝난다는 의미이다.

서브태스크 2 (40점)

• 0 ≤ A, B ≤ 300

예제 입력 1

1
2
3
4

0 0 3
1 B 3
4 R 2
7 R 2

예제 출력 1

1
2
3
4

3
1 2 3
4
4 5 6 7

예제 입력 2

1
2
3
4
5

2 3 4
1 B 3
4 R 2
6 B 2
12 R 1

예제 출력 2

1
2
3
4

5
1 2 4 5 7
3
3 6 8

출처

• University > 아주대학교 > 2019 아주대학교 프로그래밍 경시대회 APC - Div.1 B번
• University > 아주대학교 > 2019 아주대학교 프로그래밍 경시대회 APC - Div.2 B번
  • 문제를 만든 사람: Acka, spectaclehong

알고리즘 분류

• 구현
• 자료 구조
• 우선순위 큐
• 큐

소스코드 (Heap 이용)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

import sys
import heapq

input = sys.stdin.readline

s_time, j_time, customer_count = map(int, input().split())  # 상민 포장시간, 지수 포장시간, 손님수
pacakage_list = []  # 포장시작 시간 리스트
s_end, j_end = 0, 0  # 상민, 지수 포장 끝난 시간

for _ in range(customer_count):
    start_time, color, present_count = input().rstrip().split()  # 주문시각, 색깔, 개수
    start_time = int(start_time)

    if color == 'B':  # 상민

        # 상민 포장 주문시각이 포장끝난 시각보다 먼저일 경우
        # 주문시각(포장시작시각)을 포장끝난 시점으로 변경해준다.
        start_time = max(start_time, s_end)

        for i in range(int(present_count)):  # 주문 개수만큼 반복
            heapq.heappush(pacakage_list, [start_time, 'B'])  # 상민 포장시작 시간 리스트에 저장
            start_time += s_time  # 기존 포장시작시간에 포장에 걸리는 시간 더하기
            s_end = start_time  # 포장끝난 시간은 포장시작시간+포장에 걸리는 시간

    elif color == 'R':  # 지수
        start_time = max(start_time, j_end)

        for i in range(int(present_count)):
            heapq.heappush(pacakage_list, [start_time, 'R'])
            start_time += j_time
            j_end = start_time

s_present, j_present = [], []  # 상민, 지수가 포장한 선물리스트

for i in range(1, len(pacakage_list) + 1):
    present = heapq.heappop(pacakage_list)
    if present[1] == 'B':
        s_present.append(i)
    else:
        j_present.append(i)

print(len(s_present))
print(*s_present)
print(len(j_present))
print(*j_present)

소스코드 (Queue 이용)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

import sys
from collections import deque

input = sys.stdin.readline

s_time, j_time, customer_count = map(int, input().split())  # 상민 포장시간, 지수 포장시간, 손님수
sangmin = deque()  # 상민 포장시작 시간 리스트
jisu = deque()  # 지수 포장시작 시간 시간 리스트
s_end, j_end = 0, 0  # 상민, 지수 포장 끝난 시간

for _ in range(customer_count):
    start_time, color, present_count = input().rstrip().split()  # 주문시각, 색깔, 개수
    start_time = int(start_time)

    if color == 'B':  # 상민
        start_time = max(start_time, s_end)
        # if start_time < s_end:  # 상민 포장 주문시각이 포장끝난 시각보다 먼저일 경우
        #     start_time = s_end  # 주문시각(포장시작시각)을 포장끝난 시점으로 변경해준다.

        for i in range(int(present_count)):  # 주문 개수만큼 반복
            sangmin.append([start_time, 'B'])  # 상민 포장시작 시간 리스트에 저장
            start_time += s_time  # 기존 포장시작시간에 포장에 걸리는 시간 더하기
            s_end = start_time  # 포장끝난 시간은 포장시작시간+포장에 걸리는 시간

    elif color == 'R':  # 지수
        start_time = max(start_time, j_end)
        # if start_time < j_end:
        #     start_time = j_end

        for i in range(int(present_count)):
            jisu.append([start_time, 'R'])
            start_time += j_time
            j_end = start_time

total_list = sangmin + jisu
total_list = sorted(total_list, key=lambda x: [x[0], x[1]])

s_present, j_present = [], []  # 상민, 지수가 포장한 선물리스트

for idx, present in enumerate(total_list):
    if present[1] == 'B':
        s_present.append(idx + 1)
    else:
        j_present.append(idx + 1)

print(len(s_present))
print(*s_present)
print(len(j_present))
print(*j_present)