[Gold III] 인기도 조사 - 2835

문제 링크

성능 요약

메모리: 204196 KB, 시간: 1884 ms

분류

자료 구조, 느리게 갱신되는 세그먼트 트리, 누적 합, 세그먼트 트리

제출 일자

2025년 3월 10일 23:26:53

문제 설명

최근에 상근이가 살고 있는 나라에서는 인구 조사가 있었다. 사실 이번 인구 조사의 진짜 이유는 바로 텔레비전 인기도 조사이다.

각 사람이 텔레비전을 시청한 시간은 아래와 같은 형식이다.

HH:MM:SS - HH:NN:SS

앞 시간은 그 사람이 텔레비전을 시청하기 시작한 시간이며, 다음 시간은 시청을 마친 시간이다. 사람들은 그 구간의 가장 처음과 마지막 초에도 텔레비전을 시청한다. 만약, 어떤 사람이 자정이 넘기 전(23:45:30) 에 텔레비전을 시작했다면, 다음날 텔레비전 시청을 종료한다. (01:15:00)

모든 데이터를 수집했고, 이제 이 데이터를 분석하려고 한다.

어떤 초의 인기도는 그 초에 티비를 보고 있던 사람의 수로 나타낼 수 있다. 또, 구간의 인기도는 구간에 포함되는 초의 인기도의 합을 그 구간의 길이로 나눈 값이다.

Q개의 구간이 주어졌을 때, 그 구간의 인기도를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 살고 있는 나라의 국민의 수 N이 주어진다. (N ≤ 100,000)

다음 N개 줄에는 각 사람이 티비를 시청한 구간이 문제에서 설명한 대로 주어진다. (0 ≤ HH ≤ 23, 0 ≤ MM ≤ 59, 0 ≤ SS ≤ 59)

다음 줄에는 인기도를 조사하려고 하는 구간의 수 Q가 주어진다. (Q ≤ 100,000)

다음 Q개 줄에는 인기도를 구하려고 하는 구간이 같은 형식으로 주어진다.

출력

총 Q개의 구간에 대해서 각 구간의 인기도를 출력한다. 정답과의 오차는 최대 10-6까지 허용한다.

문제 풀이

코드

누적합 풀이

/**
 * Author: nowalex322, Kim HyeonJae
 */

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    static int N, Q;
    static final int END = 60*60*24;
    static int[] prefixSum;
    static long[] time;
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
//        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_2835_인기도조사/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        prefixSum = new int[24 * 60 * 60 + 1];
        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            st = new StringTokenizer(line, " :-");
            int start = calTime(st);
            int end = calTime(st);

            if(start <= end){
                prefixSum[start]++;
                prefixSum[end+1]--;
            }
            else{
                prefixSum[start]++;
                prefixSum[END]--;
                prefixSum[0]++;
                prefixSum[end+1]--;
            }
        }
        for (int i = 1; i <= END; i++) {
            prefixSum[i] += prefixSum[i-1];
        }

        time = new long[END];
        for (int i = 0; i < END; i++) {
            if(i==0) time[0] = prefixSum[0];
            else time[i] = time[i-1] + prefixSum[i];
        }

        Q = Integer.parseInt(br.readLine());
        while(Q-->0){
            String line = br.readLine();
            st = new StringTokenizer(line, " :-");
            int start = calTime(st);
            int end = calTime(st);

            double avg = 0;

            if(start <= end){
                if(start != 0) avg = (double) (time[end] - time[start - 1]) / (end+1-start);
                else avg = (double) time[end] / (end+1-start);
            }
            else{
                avg = (double) ((time[END - 1] - time[start - 1]) + time[end]) / ((END-start) + (end+1));
            }
            sb.append(String.format("%.10f", avg)).append("\n");
        }

        System.out.println(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }

    private int calTime(StringTokenizer st){
        return 3600 * Integer.parseInt(st.nextToken()) + 60 * Integer.parseInt(st.nextToken()) + Integer.parseInt(st.nextToken());
    }
}

---

세그먼트트리 + Lazy Propagation 풀이

/**
 * Author: nowalex322, Kim HyeonJae
 */

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static final int SIZE = 24 * 60 * 60;
    static int N, Q;
    static long[] tree;
    static long[] lazy;
    static long total = 0; // 모든 인기도의 합
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
//        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_2835_인기도조사/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int h = (int) Math.ceil(Math.log(SIZE) / Math.log(2));
        int treeSize = 1 << (h+1);
        tree = new long[treeSize];
        lazy = new long[treeSize];

        N = Integer.parseInt(br.readLine());
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " :-");
            int start = calTime(st);
            int end = calTime(st);

            if(start <= end){
                update(1, start, end, 0, SIZE-1);
                total += end+1 - start;
            }
            else{
                update(1, start, SIZE-1, 0, SIZE-1);
                update(1, 0, end, 0, SIZE-1);
                total += SIZE-start + end+1;
            }
        }

        Q = Integer.parseInt(br.readLine());
        while(Q-->0){
            st = new StringTokenizer(br.readLine(), " :-");
            int start = calTime(st);
            int end = calTime(st);

            if(start <= end){
                long sum = query(1, start, end, 0, SIZE-1);
                double res = (double)sum / (end+1 - start);
                sb.append(String.format("%.10f", res)).append("\n");
            }
            else{ // end+1 부터 start-1을 제외시키기
                long sum = total - query(1, end+1, start-1, 0, SIZE-1);
                double res = (double)sum / (SIZE - (start-(end+1)));
                sb.append(String.format("%.10f", res)).append("\n");
            }
        }
        System.out.println(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }

    /**
     *
     * @param node : 현재노드
     * @param start : 업데이트할 구간 시작점
     * @param end : 업데이트할 구간 끝점
     * @param from : 노드가 담당하는 구간 시작점
     * @param to : 노드가 담당하는 구간 끝점
     */
    private void update(int node, int start, int end, int from, int to) {
        updateLazy(node, from, to);

        if(to < start || end < from) return;

        // 업데이트할 구간이 지금노드범위 완전 포함하면
        if(start <= from && to <= end){
            tree[node] += (to+1 - from); // 구간만큼 인기도 1씩 증가

            // 구간이 있으면 더 아래로 자식한테 lazy전파
            if(from != to){
                lazy[node*2] += 1;
                lazy[node*2+1] += 1;
            }
            return;
        }

        int mid = from + (to - from) / 2;
        update(node*2, start, end, from, mid);
        update(node*2+1, start, end, mid+1, to);
        tree[node] = tree[node*2] + tree[node*2+1];
    }

    /**
     *
     * @param node : 현재노드
     * @param start : 업데이트할 구간 시작점
     * @param end : 업데이트할 구간 끝점
     * @param from : 노드가 담당하는 구간 시작점
     * @param to : 노드가 담당하는 구간 끝점
     * @return : 구간 값
     */
    private long query(int node, int start, int end, int from, int to){
        updateLazy(node, from, to);

        if(end < from || to < start) return 0;

        if(start <= from && to <= end) return tree[node];

        int mid = from + (to - from) / 2;
        return query(node*2, start, end, from, mid) + query(node*2+1, start, end, mid+1, to);
    }

    // 현재 노드의 lazy 값 반영
    private static void updateLazy(int node, int from, int to) {
        if(lazy[node] != 0) {
            tree[node] += (to+1 - from) * lazy[node];
            if(from != to){
                lazy[node*2] += lazy[node];
                lazy[node*2+1] += lazy[node];
            }
            lazy[node] = 0;
        }
    }

    private int calTime(StringTokenizer st){
        return 3600 * Integer.parseInt(st.nextToken()) + 60 * Integer.parseInt(st.nextToken()) + Integer.parseInt(st.nextToken());
    }
}