방과후
ALGORITHM NOTE약 2분

BOJ 29754 - 세상에는 많은 유튜버가 있고, 그중에서 버츄얼 유튜버도 존재한다

진짜 버튜버 감별전, 방송표부터 까보자!

#algorithm#boj#silver#implementation#data-structures#string#hash-set
아카이브로 돌아가기

문제 링크

문제

세상에는 많은 유튜버가 있고, 그중에는 버츄얼 유튜버도 존재한다. 매주 55회, 매주 총 6060시간 이상 라이브 방송을 하는 버츄얼 유튜버를 진짜 버츄얼 유튜버라고 한다. 형식이는 버츄얼 유튜버를 좋아하는데 그중 진짜 버츄얼 유튜버들을 찾고 싶어 한다. NN개의 줄에 유튜버의 이름, 방송 날짜, 방송 시작 시각, 방송 종료 시각이 주어질 때 진짜 버츄얼 유튜버의 이름을 사전 순으로 출력하시오.

날짜는 11일부터 시작이고 11일은 일요일이다. 일주일은 일요일부터 토요일까지로 한다.

입력

첫 번째 줄에 방송의 수 NN과 형식이가 방송을 마지막으로 본 날짜 MM이 공백으로 구분되어 주어진다. (1≤N≤36 400;(1 \leq N \leq 36\,400; 7≤M≤364;7 \leq M \leq 364; MM은 77의 배수)) 

두 번째 줄부터 NN줄에 걸쳐 name day hh:mm hh:mm 형식으로 버츄얼 유튜버의 이름, 방송 날짜, 방송 시작 시각, 방송 종료 시각이 공백으로 구분되어 주어진다. (1≤day≤M)(1 \leq \text{day} \leq M) 시각 형식은 2424시간제를 사용한다. (0≤hh≤23;(0 \le \text{hh} \le 23; 0≤mm≤59)0 \le \text{mm} \le 59) 

이름(name)은 길이가 최대 2020자인 공백 없는 문자열이고, 영어 소문자로만 이루어져 있다. 버츄얼 유튜버의 이름은 서로 다르므로 이름으로 구분할 수 있으며, 최대 100100명 존재한다.

방송은 한 번에 최대 2323시간 5959분간 진행할 수 있으며, 전날에 방송을 시작하여 자정을 넘겨 다음 날까지 진행하는 경우는 없다. 즉, 방송 시작 날짜와 방송 종료 날짜는 항상 같다. 또한, 방송은 하루에 최대 한 번 진행한다.

출력

진짜 버츄얼 유튜버의 이름을 사전 순으로 한 줄에 하나씩 출력하시오. 만약 진짜 버츄얼 유튜버가 없다면 -1을 출력하시오.

풀이

이 문제는 방송 기록을 이름별로 묶은 뒤, 주차마다 조건을 만족하는지 확인하는 구현 문제다. 먼저 한 방송의 길이를 분 단위로 바꿔 두면 주간 합산 시간을 훨씬 다루기 쉬워진다.

코드에서는 Map<String, List<Broadcast>>로 유튜버별 방송 이력을 모은 뒤, 각 이름에 대해 진짜 버튜버 조건을 검사한다. 날짜를 기준으로 주차를 나누고, 각 주차마다 방송 횟수와 총 방송 시간을 함께 확인하는 구조다.

핵심은 입력을 바로 처리하려 하지 말고, 이름별 기록으로 한 번 정리한 뒤 검사를 시작하는 것이다. 시간 문자열을 분으로 바꾸는 전처리까지 끝나면 이후 로직은 비교적 차분하게 구현할 수 있다.

코드

java
import java.io.*;
import java.util.*;
 
public class Main {
 
    static class Broadcast {
        int day, startTime, endTime;
        Broadcast(int day, int startTime, int endTime) {
            this.day = day;
            this.startTime = startTime;
            this.endTime = endTime;
        }
    }
 
    static int M;
    static Map<String, List<Broadcast>> youtubers = new HashMap<>();
    static StringBuilder sb = new StringBuilder();
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            String name = st.nextToken();
            int day = Integer.parseInt(st.nextToken());
            int startTime = timeToMin(st.nextToken());
            int endTime = timeToMin(st.nextToken());
 
            if (!youtubers.containsKey(name))
                youtubers.put(name, new ArrayList<>());
            youtubers.get(name).add(new Broadcast(day, startTime, endTime));
        }
 
        solve();
        System.out.println(sb);
    }
 
    static int timeToMin(String time) {
        String[] parts = time.split(":");
        int hour = Integer.parseInt(parts[0]);
        int minute = Integer.parseInt(parts[1]);
        return hour * 60 + minute;
    }
 
    static void solve() {
        List<String> realVirtualYoutubers = new ArrayList<>();
 
        for (String name : youtubers.keySet()) {
            List<Broadcast> history = youtubers.get(name);
 
            if (checkReal(history))
                realVirtualYoutubers.add(name);
        }
 
        if (realVirtualYoutubers.isEmpty())
            sb.append(-1);
        else {
            Collections.sort(realVirtualYoutubers);
            for (String name : realVirtualYoutubers)
                sb.append(name).append('\n');
        }
    }
 
    static boolean checkReal(List<Broadcast> history) {
        int totalWeeks = M / 7;
 
        int[] weeklyTime = new int[totalWeeks];
        int[] weeklyCount = new int[totalWeeks];
 
        for (Broadcast broadcast : history) {
            int idx = (broadcast.day - 1) / 7;
            weeklyTime[idx] += (broadcast.endTime - broadcast.startTime);
            weeklyCount[idx]++;
        }
 
        for (int i = 0; i < totalWeeks; i++)
            if (weeklyTime[i] < 3600 || weeklyCount[i] < 5)
                return false;
 
        return true;
    }
}

복잡도

  • 시간 복잡도: 방송 기록을 모으고 이름별 주차 배열을 확인한 뒤 결과를 정렬하므로 O(N+U⋅W+Rlog⁡R)O(N + U \cdot W + R \log R)이다.
  • 공간 복잡도: 방송 기록과 주차별 집계 배열을 저장하므로 O(N+W)O(N + W)이다.

마무리

주차별 방송 횟수와 누적 시간을 따로 세면 진짜 버튜버 판정이 깔끔하게 떨어진다.