Logo
(追記) (追記ここまで)

25244번 - 가희와 영상 추천 시스템

시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 512 MB145251311.404%

문제

가희는 YOTUBE에서 영상을 보고 있습니다. 가희가 R를 입력했을 때, 고유 번호가 id인 영상의 연관 지수는 아래와 같이 정의됩니다.

  • 가희가 R를 입력하기 전 72시간 전부터 R를 입력할 때 까지
    • 고유 번호가 id인 영상을 본 횟수 v
    • 고유 번호가 id인 영상이 속한 카테고리를 C라 했을 때, 카테고리 C에 속하는 영상을 본 횟수 c
  • 라고 했을 때, v와 c를 더한 값

YOTUBE에 있는 추천 영상은 아래 기준에 따라 순위가 결정됩니다.

  1. 연관 지수가 높은 것
  2. 연관 지수가 같다면, 영상 id가 작은 것부터

가희가 R를 입력할 때마다, 추천 영상 1위의 영상에 대한 정보를 출력해 주세요.

입력

1번째 줄에 YOTUBE에 있는 영상 개수 N과 이벤트의 개수 E가 주어집니다.

그 다음 줄부터 N개의 줄에 VIDEO_NAME과 VIDEO_CATEGORY와 VIDEO_ID가 공백으로 구분되어 주어집니다. 이때

  • 문자열 VIDEO_NAME은 공백, 숫자, 소문자로만 이루어져 있으며, 공백으로 시작하거나 끝나지 않습니다.
  • 문자열 VIDEO_CATEGORY는 숫자, 소문자로만 이루어져 있습니다.
  • VIDEO_ID는 1이상 109 이하의 정수입니다.

그 다음 줄부터 E개의 줄에 아래 형식 중 하나가 주어집니다.

  • EVENT_TIME VIDEO_ID
    • EVENT_TIME에 가희는 고유 번호가 VIDEO_ID인 영상을 봅니다.
  • EVENT_TIME R
    • EVENT_TIME에 가희는 추천 영상 1위의 영상 정보를 알고 싶어합니다.

이때, VIDEO_ID는 YOTUBE에 있는 영상 id만 주어집니다.

출력

R 연산이 들어올 때마다, 추천 영상 1위의 동영상 id를 출력해 주세요.

제한

  • 1 ≤ E ≤ 5 × 105
  • 1 ≤ N≤ 5 × 105
  • 이벤트 E개가 일어난 시각은 모두 다르며, 먼저 일어난 순서대로 주어집니다.
  • 주어지는 N개의 영상 id는 모두 다릅니다.
  • R 연산이 일어나기 72시간 전부터 1초 전까지 본 영상이 최소 하나 이상 있습니다.
  • VIDEO_CATEGORY의 길이는 15를 넘지 않고, VIDEO_NAME의 길이는 40을 넘지 않습니다.
  • EVENT_TIME은 2000년 1월 1일 00:00:00 이후이며, 이 대회가 시작한 시각 이전입니다. 또한 EVENT_TIME은 YYYY-MM-DD hh:mm:ss 형식으로 주어집니다.
  • R 연산은 최소 한 번 이상 들어옵니다.

예제 입력 1 

4 6
feel my rhythm 1 hour music 2
fairy wink music 5
yoasobi maybe music 3
super rapid train kyoto to osaka train 1
2022年01月01日 22:23:34 1
2022年01月02日 22:20:00 2
2022年01月03日 11:11:11 R
2022年01月03日 12:12:33 5
2022年01月05日 22:20:00 R
2022年01月05日 22:22:01 R

예제 출력 1 

1
2
5

2, 3, 5번 영상은 music카데고리에, 1번 영상은 train카데고리에 속합니다. 2022년 1월 3일 11시 11분 11초에 R연산이 들어왔을 때 각 영상의 v와 c값은 [표 1]과 같습니다.

id 카데고리 v c
1 train 1 1
2 music 1 1
3 music 0 1
5 music 0 1

[표 1] 1번째 R연산이 들어왔을 때 각 영상의 연관 지수 값

v + c 값이 제일 큰 것은 1번과 2번 영상입니다. 둘 중 id가 더 작은 것은 1번이므로, 1번째 R연산에 대한 답은 1이 됩니다.

id 카데고리 v c
1 train 0 0
2 music 1 2
3 music 0 2
5 music 1 2

[표 2] 2번째 R연산이 들어왔을 때 각 영상의 연관 지수 값

2번째 R연산이 들어온 시각은 2022년 1월 5일 22시 20분 00초였습니다. 이 때, 1번 영상은 72시간 전에 본 영상이 아니므로, 추천 시스템의 집계에서 제외됩니다. v + c 값이 제일 큰 것은 2번과 5번이고, 이 중 2가 5보다 작으므로, 2번째 R연산에 대한 답은 2가 됩니다.

id 카데고리 v c
1 train 0 0
2 music 0 1
3 music 0 1
5 music 1 1

[표 3] 3번째 R연산이 들어왔을 때 각 영상의 연관 지수 값

다음 3번째 R연산이 수행될 때, 2번이 집계에서 제외됩니다. v + c 의 값은 [표 3]과 같으므로, 3번째 R연산에 대한 값은 5가 됩니다.

예제 입력 2 

5 3
produce 48 boombayah audition 2
produce 48 mamma mia audition 5
yoasobi racing into the night music 3
hkt castle moves now music 1
gag concert ep 283 entertainment 4
2022年01月01日 22:23:34 2
2022年01月02日 22:20:00 5
2022年01月03日 11:11:11 R

예제 출력 2 

2

예제 입력 3 

3 7
maplestory swoo normal mode game 2
maplestory swoo hard mode game 1
hkt 48 outing ep 49 entertainment 5
2022年01月01日 22:23:34 2
2022年01月01日 22:23:36 2
2022年01月02日 22:20:00 1
2022年01月04日 22:23:37 R
2022年01月05日 22:19:57 5
2022年01月05日 22:19:58 R
2022年01月05日 22:20:01 R

예제 출력 3 

1
1
5

예제 입력 4 

7 6
yoasobi love letter music 1
moringgu musume get you music 2
gahui hate jusagi daliy 3
produce 48 get you audition 4
gahui meet friend daliy 5
may 2022 top 100 music music 6
akb fairy wink music 7
2021年12月12日 00:00:00 2
2021年12月12日 00:11:00 4
2021年12月12日 00:22:00 1
2021年12月15日 00:00:00 R
2021年12月15日 00:11:00 6
2021年12月15日 00:11:10 R

예제 출력 4 

1
1

힌트

출처

Contest > BOJ User Contest > 가희와 함께 하는 코딩 테스트 > 가희와 함께 하는 코딩테스트 4회 G번

(追記) (追記ここまで)

출처

대학교 대회

  • 사업자 등록 번호: 541-88-00682
  • 대표자명: 최백준
  • 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
  • 전화번호: 02-521-0487 (이메일로 연락 주세요)
  • 이메일: contacts@startlink.io
  • 통신판매신고번호: 제 2017-서울서초-2193 호

AltStyle によって変換されたページ (->オリジナル) /