[백준] 2002번 추월

[백준] 2002번 추월

출처: [백준] 2002번 추월


시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 2040 894 757 44.766%

문제

대한민국을 비롯한 대부분의 나라에서는 터널 내에서의 차선 변경을 법률로 금하고 있다. 조금만 관찰력이 있는 학생이라면 터널 내부에서는 차선이 파선이 아닌 실선으로 되어 있다는 것을 알고 있을 것이다. 이는 차선을 변경할 수 없음을 말하는 것이고, 따라서 터널 내부에서의 추월은 불가능하다.

소문난 명콤비 경찰 대근이와 영식이가 추월하는 차량을 잡기 위해 한 터널에 투입되었다. 대근이는 터널의 입구에, 영식이는 터널의 출구에 각각 잠복하고, 대근이는 차가 터널에 들어가는 순서대로, 영식이는 차가 터널에서 나오는 순서대로 각각 차량 번호를 적어 두었다.

N개의 차량이 지나간 후, 대근이와 영식이는 자신들이 적어 둔 차량 번호의 목록을 보고, 터널 내부에서 반드시 추월을 했을 것으로 여겨지는 차들이 몇 대 있다는 것을 알게 되었다. 대근이와 영식이를 도와 이를 구하는 프로그램을 작성해 보자.


입력

입력은 총 2N+1개의 줄로 이루어져 있다. 첫 줄에는 차의 대수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 대근이가 적은 차량 번호 목록이 주어지고, N+2째 줄부터 N개의 줄에는 영식이가 적은 차량 번호 목록이 주어진다. 각 차량 번호는 6글자 이상 8글자 이하의 문자열로, 영어 대문자(‘A’-‘Z’)와 숫자(‘0’-‘9’)로만 이루어져 있다.

같은 차량 번호가 두 번 이상 주어지는 경우는 없다.


출력

첫째 줄에 터널 내부에서 반드시 추월을 했을 것으로 여겨지는 차가 몇 대인지 출력한다.


예제 입력 1

1
2
3
4
5
6
7
8
9
4
ZG431SN
ZG5080K
ST123D
ZG206A
ZG206A
ZG431SN
ZG5080K
ST123D

예제 출력 1

1
1

예제 입력 2

1
2
3
4
5
6
7
8
9
10
11
5
ZG508OK
PU305A
RI604B
ZG206A
ZG232ZF
PU305A
ZG232ZF
ZG206A
ZG508OK
RI604B

예제 출력 2

1
3

예제 입력 3

1
2
3
4
5
6
7
8
9
10
11
5
ZG206A
PU234Q
OS945CK
ZG431SN
ZG5962J
ZG5962J
OS945CK
ZG206A
PU234Q
ZG431SN

예제 출력 3

1
2

출처


알고리즘 분류


소스코드

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

input = sys.stdin.readline

N = int(input())

count = 0
input_car = {}
output_car = []

for i in range(N):
input_car[input().rstrip()] = i

for i in range(N):
output_car.append(input().rstrip())

for i in range(N - 1):
for j in range(i + 1, N):
if input_car[output_car[i]] > input_car[output_car[j]]:
count += 1
break

print(count)

[백준] 10546번 배부른 마라토너

[백준] 10546번 배부른 마라토너

출처: [백준] 10546번 배부른 마라토너


시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 2023 867 681 44.597%

문제

마라토너라면 국적과 나이를 불문하고 누구나 참가하고 싶어하는 백준 마라톤 대회가 열린다. 42.195km를 달리는 이 마라톤은 모두가 참가하고 싶어했던 만큼 매년 모두가 완주해왔다. 단, 한 명만 빼고!

모두가 참가하고 싶어서 안달인데 이런 백준 마라톤 대회에 참가해 놓고 완주하지 못한 배부른 참가자 한 명은 누굴까?


입력

첫째 줄에는 참가자 수 N이 주어진다. (1 ≤ N ≤ 105)

N개의 줄에는 참가자의 이름이 주어진다.

추가적으로 주어지는 N-1개의 줄에는 완주한 참가자의 이름이 쓰여져 있다.

참가자들의 이름은 길이가 1보다 크거나 같고, 20보다 작거나 같은 문자열이고, 알파벳 소문자로만 이루어져 있다.

참가자들 중엔 동명이인이 있을 수도 있다.


출력

마라톤을 완주하지 못한 참가자의 이름을 출력한다.


예제 입력 1

1
2
3
4
5
6
3
leo
kiki
eden
eden
kiki

예제 출력 1

1
leo

예제 입력 2

1
2
3
4
5
6
7
8
9
10
5
marina
josipa
nikola
vinko
filipa
josipa
filipa
marina
nikola

예제 출력 2

1
vinko

예제 입력 3

1
2
3
4
5
6
7
8
4
mislav
stanko
mislav
ana
stanko
ana
mislav

예제 출력 3

1
mislav

출처


알고리즘 분류


소스코드

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

input = sys.stdin.readline

N = int(input())

participants = {}
for _ in range(N):
participant = input().rstrip()
if participant in participants:
participants[participant] += 1
else:
participants[participant] = 0

for _ in range(N - 1):
participants[input().rstrip()] += 1

for key, value in participants.items():
if value % 2 == 0:
print(key)
break
else:
continue

[백준] 16165번 걸그룹 마스터 준석이

[백준] 16165번 걸그룹 마스터 준석이

출처: [백준] 16165번 걸그룹 마스터 준석이


시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 (추가 시간 없음) 128 MB 1680 1055 788 63.446%

문제

정우는 소문난 걸그룹 덕후이다. 정우의 친구 준석이도 걸그룹을 좋아하지만 이름을 잘 외우지 못한다는 문제가 있었다. 정우는 친구를 위해 걸그룹 개인과 팀의 이름을 검색하여 외우게 하는 퀴즈 프로그램을 만들고자 한다.


입력

첫 번째 줄에는 총 입력 받을 걸그룹의 수 N(0 < N < 100)과 맞혀야 할 문제의 수 M(0 < M < 100)을 입력받는다.

두 번째 줄부터는 각 걸그룹마다 팀의 이름, 걸그룹의 인원 수, 멤버의 이름을 한 줄씩 차례대로 입력받는다. 팀과 멤버의 이름은 최대 100글자이며, 모든 글자는 알파벳 소문자이다. 하나의 걸그룹이나 서로 다른 두 걸그룹에 이름이 같은 두 멤버가 있는 경우는 없다.

그 다음 줄부터는 M개의 퀴즈를 입력받는다. 각각의 퀴즈는 두 줄로 이루어져 있으며, 팀의 이름이나 멤버의 이름이 첫 줄에 주어지고 퀴즈의 종류를 나타내는 0 또는 1이 두 번째 줄에 주어진다. 퀴즈의 종류가 0일 경우 팀의 이름이 주어지며, 1일 경우 멤버의 이름이 주어진다.


출력

첫 번째 줄부터 차례대로 퀴즈에 대한 답을 출력한다. 퀴즈의 종류가 0일 경우 해당 팀에 속한 멤버의 이름을 사전순으로 한 줄에 한 명씩 출력한다. 퀴즈의 종류가 1일 경우 해당 멤버가 속한 팀의 이름을 출력한다.


예제 입력 1

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
3 4
twice
9
jihyo
dahyeon
mina
momo
chaeyoung
jeongyeon
tzuyu
sana
nayeon
blackpink
4
jisu
lisa
rose
jenny
redvelvet
5
wendy
irene
seulgi
yeri
joy
sana
1
wendy
1
twice
0
rose
1

예제 출력 1

1
2
3
4
5
6
7
8
9
10
11
12
twice
redvelvet
chaeyoung
dahyeon
jeongyeon
jihyo
mina
momo
nayeon
sana
tzuyu
blackpink

출처


알고리즘 분류


소스코드

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

input = sys.stdin.readline

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

Team = {}
for _ in range(N):
team_name = input().rstrip()
Team[team_name] = []
members = int(input())
for _ in range(members):
Team[team_name].append(input().rstrip())

for _ in range(M):
name = input().rstrip()
flag = int(input())
if flag: # 팀 이름만 출력
for team, member in Team.items():
if name in member:
print(team)
else: # 멤버 전체 사전순 출력
print('\n'.join(sorted(Team[name])))

[백준] 17264번 I AM IRONMAN

[백준] 17264번 I AM IRONMAN

출처: [백준] 17264번 I AM IRONMAN


시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 788 388 358 50.210%

문제

다들 문제 제목을 보고 요즘 가장 핫한 영화를 생각했겠지만 이 이야기는 LUL(League Us Legends) 게임에서 아이언(Iron) 티어에 있는 형동이의 슬픈 이야기이다. LUL에서 티어는 게임 실력을 판가름할 수 있는 지표이다. 그중 아이언 티어는 가장 낮은 단계에 위치해 있다. 친구인 강엽이와 건홍이에게 “Ironman”이라며 게임을 못한다고 놀림당하던 형동이는 꼭 아이언 티어에서 벗어나겠다고 결심했다. 하지만 형동이는 자신의 실력으로 절대 아이언(Iron) 티어에서 벗어나지 못하는 것을 알고 있다. LUL은 두 명의 플레이어가 같이 팀이 되어 하는 게임이기 때문에 자신이 못해도 게임에서 이길 수 있고 자신이 잘해도 게임은 질 수 있다. 형동이는 게임은 못하지만 머리가 매우 똑똑하여 LUL 게임을 해킹하여서 몇몇 플레이어와 같이 게임을 하게 되면 게임의 승패가 어떻게 되는지 알게 되었다. 하지만 해킹을 통하여 알아내지 못한 플레이어와 같이 게임을 하는 경우 형동이가 매우 못하기 때문에 같은 팀원이 아무리 잘해도 반드시 진다.

img

위와 같은 경우에서 “JIHOON”과 같이 게임을 하는 경우 20점(W = 20)을 획득하는 반면에 “GANGYEOP”이나 “MINSUNG”과 같이 게임 하는 경우 경우 15점(L = 15)을 잃게 된다. 뿐만 아니라, 해킹을 통해 알지 내지 못한 플레이어를 만나게 되는 경우 형동이가 매우 못하여 지기 때문에 15점을 잃게 된다. (단, 계속 지더라도 점수는 0점 밑으로 떨어지지 않는다.)

형동이가 N번에 게임을 통해서 아이언 티어에서 탈출한 경우 형동이는 “I AM NOT IRONMAN”이라고 외치지만 탈출하지 못한 경우 “I AM IRONMAN”이라고 외친다.

여기서 아이언 티어를 탈출하기 위해서 100점 (G = 100) 이상이 되어야 했다면 9번째 게임(주황색 사각형)을 하고 아이언 티어를 탈출하였기 때문에 형동이는 “I AM NOT IRONMAN”이라고 외친다. 아이언 티어에서 탈출한 경우 그 이후에 게임은 신경쓰지 않는다.

하지만 만약 탈출하기 위해서 200점(G = 200) 이상이 되어야 한다고 했을 경우 형동이는 아이언 티어를 탈출하지 못했기 때문에 “I AM IRONMAN”이라고 외치게 된다.

과연 형동이는 게임이 끝난 후 어떤 대사를 할 지 우리가 맞춰보자.


입력

첫 번째 줄에는 총 게임 횟수 N과 해킹을 통해 얻은 플레이어 정보의 수 P가 주어진다. (NP는 1,000이하의 자연수)

그리고 두 번째 줄에는 이긴 경우 획득 점수 W와 졌을 때 떨어지는 점수 L, 그리고 IRON 티어에서 벗어나기 위한 점수 G가 주어진다. (0 ≤ W, L ≤ 100, 1 ≤ G ≤ 100,000, 이 때, W, L, G는 정수)

그리고 다음 P개의 줄에는 플레이어의 이름과 무조건 이길 수 있는 경우 W, 무조건 지는 경우 L이라는 단어가 플레이어 이름과 쌍으로 나온다.

그리고 그 다음 N개의 줄에는 같이 게임을 하는 플레이어의 이름이 나온다.

플레이어 이름은 반드시 대문자로 나오며 길이는 20이 넘지 않는다.


출력

0점부터 시작하였을 때 형동이가 아이언 티어에서 벗어나지 못한 경우 "I AM IRONMAN!!", 아이언 티어에서 벗어난 경우 “I AM NOT IRONMAN!!”을 출력한다.


예제 입력 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
10 3
20 15 100
JIHOON W
GANGYEOP L
MINSUNG L
JIHOON
MYEONGKI
GANGYEOP
MINSUNG
JIHOON
JIHOON
JIHOON
JIHOON
JIHOON
MINSUNG

예제 출력 1

1
I AM NOT IRONMAN!!

예제 입력 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
10 3
20 15 100
JIHOON W
GANGYEOP L
MINSUNG L
JIHOON
GANGYEOP
JISUP
MINSUNG
JIHOON
JIHOON
MOJI
KYUNGMIN
SOOHO
SEOKGYE

예제 출력 2

1
I AM IRONMAN!!

출처


알고리즘 분류


소스코드

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
import sys

input = sys.stdin.readline

N, P = map(int, input().split())

W, L, G = map(int, input().split())

hacking = {}
for _ in range(P):
name, WL = input().rstrip().split()
hacking[name] = WL

score = 0
for _ in range(N):
name = input().rstrip()
if name in hacking.keys():
if hacking[name] == 'W':
score += W
else:
score -= L
else:
score -= L

if score < 0:
score = 0
elif score >= G:
print('I AM NOT IRONMAN!!')
exit(0)

print('I AM IRONMAN!!')

[백준] 9322번 철벽 보안 알고리즘

[백준] 9322번 철벽 보안 알고리즘

출처: [백준] 9322번 철벽 보안 알고리즘


시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 1389 853 679 63.045%

문제

소희는 공개키와 개인키 한 쌍으로 보안을 유지하는 것이 매우 불편하다고 생각했다. 그래서 소희는 공개키만을 이용하는 암호화 체계를 개발했다. 이를 “철벽 보안 알고리즘”이라고 부르기로 했다. 알고리즘은 다음과 같다.

한 단어는 1~10개의 대문자(A-Z)들로 이루어진 문자열이다. 한 문장은 공백으로 구분된 단어들로 이루어졌다.

제 1 공개키는 최대 한 번만 사용된 단어들로 되어있다.

제 2 공개키는 제 1 공개키의 단어들을 재배치하여 만들어진다.

평문(암호화 되지 않은 문장)은 제 1 공개키와 같이 여러 단어들로 되어있지만, 제 1 공개키와 다르게 각 단어들은 중복이 가능하다.

암호문(암호화 된 문장)은 평문을 제 2 공개키를 만든 규칙의 반대로 재배치하여 만들어진다.

주어진 2개의 공개키와 암호문으로 평문을 복구하라.


입력

입력의 첫 줄에는 테스트 케이스의 수를 의미하는 하나의 정수가 입력된다. 정수는 100을 넘지 않는다.

각 테스트케이스마다 아래 항목들을 한 줄씩 입력받는다.

  • 한 문장의 단어 수 n (1 ≤ n ≤ 1 000)
  • 제 1 공개키
  • 제 2 공개키
  • 암호문

모든 단어들은 최소 1개, 최대 10개의 대문자들로 이루어져있다.


출력

각 케이스마다

  • 암호문을 해독한 평문

을 한 줄에 줄력한다.


예제 입력 1

1
2
3
4
5
6
7
8
9
2
4
A B C D
D A B C
C B A P
3
SECURITY THROUGH OBSCURITY
OBSCURITY THROUGH SECURITY
TOMORROW ATTACK WE

예제 출력 1

1
2
B A P C
WE ATTACK TOMORROW

출처

img


알고리즘 분류


소스코드

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

input = sys.stdin.readline

T = int(input())

for _ in range(T):
N = int(input())
first_public_key = list(input().split())
second_public_key = list(input().split())
cipher_text = list(input().split())

rule = []
for i in range(N):
rule.append(second_public_key.index(first_public_key[i]))

for i in rule:
print(cipher_text[i], end=' ')

[백준] 1302번 베스트셀러

[백준] 1302번 베스트셀러

출처: [백준] 1302번 베스트셀러


시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 8128 3653 2999 45.433%

문제

김형택은 탑문고의 직원이다. 김형택은 계산대에서 계산을 하는 직원이다. 김형택은 그날 근무가 끝난 후에, 오늘 판매한 책의 제목을 보면서 가장 많이 팔린 책의 제목을 칠판에 써놓는 일도 같이 하고 있다.

오늘 하루 동안 팔린 책의 제목이 입력으로 들어왔을 때, 가장 많이 팔린 책의 제목을 출력하는 프로그램을 작성하시오.


입력

첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고, 알파벳 소문자로만 이루어져 있다.


출력

첫째 줄에 가장 많이 팔린 책의 제목을 출력한다. 만약 가장 많이 팔린 책이 여러 개일 경우에는 사전 순으로 가장 앞서는 제목을 출력한다.


예제 입력 1

1
2
3
4
5
6
5
top
top
top
top
kimtop

예제 출력 1

1
top

출처


알고리즘 분류

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

input = sys.stdin.readline

N = int(input())

sell_items = {}

for _ in range(N):
book_name = input().rstrip()
if book_name in sell_items:
sell_items[book_name] += 1
else:
sell_items[book_name] = 1

max_sell = max(sell_items.values())

best_seller = []
for book, count in sell_items.items():
if count == max_sell:
best_seller.append(book)

print(sorted(best_seller)[0])

[백준] 2776번 암기왕

[백준] 2776번 암기왕

출처: [백준] 2776번 암기왕


시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 10889 3396 1943 27.981%

문제

연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, 연종이 하루 동안 본 정수들을 모두 ‘수첩1’에 적어 놓았다. 그것을 바탕으로 그가 진짜 암기왕인지 알아보기 위해, 동규는 연종에게 M개의 질문을 던졌다. 질문의 내용은 “X라는 정수를 오늘 본 적이 있는가?” 이다. 연종은 막힘없이 모두 대답을 했고, 동규는 연종이 봤다고 주장하는 수 들을 ‘수첩2’에 적어 두었다. 집에 돌아온 동규는 답이 맞는지 확인하려 하지만, 연종을 따라다니느라 너무 힘들어서 여러분에게 도움을 요청했다. 동규를 도와주기 위해 ‘수첩2’에 적혀있는 순서대로, 각각의 수에 대하여, ‘수첩1’에 있으면 1을, 없으면 0을 출력하는 프로그램을 작성해보자.


입력

첫째 줄에 테스트케이스의 개수 T가 들어온다. 다음 줄에는 ‘수첩 1’에 적어 놓은 정수의 개수 N(1 ≤ N ≤ 1,000,000)이 입력으로 들어온다. 그 다음 줄에 ‘수첩 1’에 적혀 있는 정수들이 N개 들어온다. 그 다음 줄에는 ‘수첩 2’에 적어 놓은 정수의 개수 M(1 ≤ M ≤ 1,000,000) 이 주어지고, 다음 줄에 ‘수첩 2’에 적어 놓은 정수들이 입력으로 M개 들어온다. 모든 정수들의 범위는 int 로 한다.


출력

‘수첩2’에 적혀있는 M개의 숫자 순서대로, ‘수첩1’에 있으면 1을, 없으면 0을 출력한다.


예제 입력 1

1
2
3
4
5
1
5
4 1 5 2 3
5
1 3 7 9 5

예제 출력 1

1
2
3
4
5
1
1
0
0
1

출처


알고리즘 분류

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

input = sys.stdin.readline

T = int(input())

for _ in range(T):
N = int(input())
N_Note = set(map(int, input().split()))

M = int(input())
M_Note = list(map(int, input().split()))

for num in M_Note:
if num in N_Note:
print(1)
else:
print(0)

[백준] 1269번 대칭 차집합

[백준] 1269번 대칭 차집합

출처: [백준] 1269번 대칭 차집합


시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 4426 2319 1763 53.295%

문제

자연수를 원소로 갖는 공집합이 아닌 두 집합 A와 B가 있다. 이때, 두 집합의 대칭 차집합의 원소의 개수를 출력하는 프로그램을 작성하시오. 두 집합 A와 B가 있을 때, (A-B)와 (B-A)의 합집합을 A와 B의 대칭 차집합이라고 한다.

예를 들어, A = { 1, 2, 4 } 이고, B = { 2, 3, 4, 5, 6 } 라고 할 때, A-B = { 1 } 이고, B-A = { 3, 5, 6 } 이므로, 대칭 차집합의 원소의 개수는 1 + 3 = 4개이다.


입력

첫째 줄에 집합 A의 원소의 개수와 집합 B의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 집합 A의 모든 원소가, 셋째 줄에는 집합 B의 모든 원소가 빈 칸을 사이에 두고 각각 주어진다. 각 집합의 원소의 개수는 200,000을 넘지 않으며, 모든 원소의 값은 100,000,000을 넘지 않는다.


출력

첫째 줄에 대칭 차집합의 원소의 개수를 출력한다.


예제 입력 1

1
2
3
3 5
1 2 4
2 3 4 5 6

예제 출력 1

1
4

출처


알고리즘 분류


소스코드

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

input = sys.stdin.readline

A, B = map(int, input().split())

set_A = set(map(int, input().split()))
set_B = set(map(int, input().split()))

AB = set_A - set_B
BA = set_B - set_A

print(len(AB) + len(BA))

[백준] 13414번 수강신청

[백준] 13414번 수강신청

출처: [백준] 13414번 수강신청


시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 6098 1293 852 20.363%

문제

국민대학교에서는 매 학기 시작 전 종합정보시스템에서 수강신청을 한다. 매 수강신청마다 아주 많은 학생들이 몰려 서버에 많은 부하가 가기 때문에, 국민대학교에서는 수강신청 부하 관리 시스템을 도입하기로 결정하였다. 새로운 관리 시스템은 다음과 같은 방식으로 동작한다.

  1. 수강신청 버튼이 활성화 된 후, 수강신청 버튼을 조금이라도 빨리 누른 학생이 대기목록에 먼저 들어간다.
  2. 이미 대기열에 들어가 있는 상태에서 다시 수강신청 버튼을 누를 경우 대기목록의 맨 뒤로 밀려난다.
  3. 잠시 후 수강신청 버튼이 비활성화 되면, 대기목록에서 가장 앞에 있는 학생부터 자동으로 수강신청이 완료되며, 수강 가능 인원이 꽉 찰 경우 나머지 대기목록은 무시하고 수강신청을 종료한다.

img

위의 표는 최대 수강 가능 인원이 3명인 알고리즘 수업에 대해 6명의 학생이 수강신청을 진행한 모습이다. 버튼이 비활성화 된 후, 먼저 규칙 1을 적용하여 클릭을 2번 이상 한 학생의 중복된 대기목록을 삭제한다. 중복된 목록을 제거한 후, 맨 앞에서부터 최대 수강 가능 인원인 3명을 선정한다. 표의 맨 오른쪽에는 그 최종결과를 나타낸 모습이다. 이와 같은 방법을 이용하여 최종적으로 수강신청에 성공한 인원을 출력하는 프로그램을 작성하시오.


입력

입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 과목의 수강 가능 인원 K(1 ≤ K ≤ 100,000)와 학생들이 버튼을 클릭한 순서를 기록한 대기목록의 길이 L(1 ≤ L ≤ 500,000)이 주어진다. 두 번째 줄부터 L개의 줄에는 수강신청을 버튼을 클릭한 학생의 학번이 클릭 순서대로 주어진다. 학번은 8자리의 숫자로 이루어져 있다.


출력

출력은 표준 출력을 사용한다. 입력받은 데이터에 대해, 수강신청 관리 시스템의 규칙을 적용한 후 수강신청에 성공한 인원의 학번을 한 줄에 1개씩 출력한다.


예제 입력 1

1
2
3
4
5
6
7
8
9
3 8
20103324
20133221
20133221
20093778
20140101
01234567
20093778
20103325

예제 출력 1

1
2
3
20103324
20133221
20140101

출처


알고리즘 분류


소스코드

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

input = sys.stdin.readline

K, L = map(int, input().split())

queue_list = {}

for i in range(L):
studentId = input().rstrip()
queue_list[studentId] = i

cnt = 0
for x in sorted(queue_list.items(), key=lambda x: x[1]):
cnt += 1
if cnt > K:
break
print(x[0])

[백준] 17219번 비밀번호 찾기

[백준] 17219번 비밀번호 찾기

출처: [백준] 17219번 비밀번호 찾기


시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 256 MB 3192 2207 1783 70.782%

문제

2019 HEPC - MAVEN League의 “비밀번호 만들기“와 같은 방식으로 비밀번호를 만든 경민이는 한 가지 문제점을 발견하였다. 비밀번호가 랜덤으로 만들어져서 기억을 못 한다는 것이었다! 그래서 경민이는 메모장에 사이트의 주소와 비밀번호를 저장해두기로 했다. 하지만 컴맹인 경민이는 메모장에서 찾기 기능을 활용하지 못하고 직접 눈으로 사이트의 주소와 비밀번호를 찾았다. 메모장에 저장된 사이트의 수가 늘어나면서 경민이는 비밀번호를 찾는 일에 시간을 너무 많이 쓰게 되었다. 이를 딱하게 여긴 문석이는 경민이를 위해 메모장에서 비밀번호를 찾는 프로그램을 만들기로 결심하였다! 문석이를 도와 경민이의 메모장에서 비밀번호를 찾아주는 프로그램을 만들어보자.


입력

첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다.

두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번호가 공백으로 구분되어 주어진다. 사이트 주소는 알파벳 소문자, 알파벳 대문자, 대시(‘-‘), 마침표(‘.’)로 이루어져 있고, 중복되지 않는다. 비밀번호는 알파벳 대문자로만 이루어져 있다. 모두 길이는 최대 20자이다.

N+2번째 줄부터 M개의 줄에 걸쳐 비밀번호를 찾으려는 사이트 주소가 한줄에 하나씩 입력된다. 이때, 반드시 이미 저장된 사이트 주소가 입력된다.


출력

첫 번째 줄부터 M개의 줄에 걸쳐 비밀번호를 찾으려는 사이트 주소의 비밀번호를 차례대로 각 줄에 하나씩 출력한다.


예제 입력 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
16 4
noj.am IU
acmicpc.net UAENA
startlink.io THEKINGOD
google.com ZEZE
nate.com VOICEMAIL
naver.com REDQUEEN
daum.net MODERNTIMES
utube.com BLACKOUT
zum.com LASTFANTASY
dreamwiz.com RAINDROP
hanyang.ac.kr SOMEDAY
dhlottery.co.kr BOO
duksoo.hs.kr HAVANA
hanyang-u.ms.kr OBLIVIATE
yd.es.kr LOVEATTACK
mcc.hanyang.ac.kr ADREAMER
startlink.io
acmicpc.net
noj.am
mcc.hanyang.ac.kr

예제 출력 1

1
2
3
4
THEKINGOD
UAENA
IU
ADREAMER

노트

입출력 방식이 느리면 여러 줄을 입력받거나 출력할 때 시간초과가 날 수 있다.

C++을 사용하고 있고 cin/cout을 사용하고자 한다면, main함수 안에 cin.tie(NULL)ios::sync_with_stdio(false)함수를 둘 다 호출해 주고, endl 대신 개행문자(\n)를 쓰자. 단, 이렇게 하면 더 이상 scanf/printf/puts/getchar/putchar 등 C의 입출력 방식을 사용하면 안 된다.

Java를 사용하고 있다면, ScannerSystem.out.println 대신 BufferedReaderBufferedWriter를 사용할 수 있다. BufferedWriter.flush는 맨 마지막에 한 번만 하면 된다.


출처


알고리즘 분류


소스코드

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

input = sys.stdin.readline

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

password = {}

for _ in range(N):
url, pwd = input().split()
password[url] = pwd

for _ in range(M):
url = input().rstrip()
print(password[url])