[자바] 백준 2835 - 인기도 조사(java)

 문제 : boj2835

---

 

필요 알고리즘 개념

• 누적합 알고리즘
  
  • 약간의 배열 테크닉을 활용하면 누적합 알고리즘 만으로 풀 수 있다.
• 세그먼트 트리 lazy propagation 또는 range update - range query 펜윅 트리
  
  • 누적합으로 풀려면 아이디어가 필요하다. 일반적으로는 세그먼트 트리 lazy propagation 혹은 펜윅 트리 응용을 통해 풀게 된다. 이하 풀이는 누적합을 통한 풀이이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  만약 세그먼트 트리 lazy propagation을 알고 있다면 그걸로 풀 수 있다. 그리고 펜윅 트리로 풀려면 '펜윅트리 글'에서 응용3(range update + range query)을 구현하면 풀 수 있다. 이 글은 누적합 알고리즘을 사용해 구현할것인데, 혹시 모른다면 이 글을 참고하자.

 

  

  이 문제에서 시간을 초로 모두 변경한다면, 0부터 24*60*60-1 = 86399로 표현할 수 있다(-1인 이유는 23시59분59초 까지이므로). 다만 누적합 알고리즘을 사용하려면 인덱스 1부터 사용하는게 더 편하므로 코드에서는 1부터 86400으로 사용한다. 시간으로 된 입력을 초로 변경하는 것은 애초에 플래수준의 문제를 풀려는 분이면 당연히 알 것이므로 넘어가겠다. 그리고 구간이 a ~ b 일 때, 당연히 b<a인 경우라면 하루를 넘긴 것이므로 그 부분도 처리해줘야 한다. 이것도 넘어가겠다.

 

 

  lazy propagation이 생각나는 문제지만, N개의 update와 Q개의 query가 서로 섞여있지 않고, update가 모두 이뤄진 후에 query가 진행되는 특징으로 인해 다음과 같이 풀 수도 있다.

 

 

두 배열을 정의하자.

(이 글에서 설명하는 d[ ]가 코드에서의 arr[ ]이다.)

c[ ] : 1~86400 각 초에 티비를 보고 있던 사람의 수(=인기도)

d[ ] : d[x] = c[x] - c[x-1] 로 정의한 배열

 

 

시청 기록 구간 처리

  [a, b] 구간에 대한 시청 기록은 다음과 같이 생각할 수 있다.

d[a]++, d[b+1]--;

왜냐하면 d[a+1] = c[a+1] - c[a]인데, c[a+1]과 c[a]는 둘 다 인기도가 +1 되어야 하므로 d[a+1]' = (c[a+1]+1) - (c[a]+1) 이 되서 d[a+1] == d[a+1]' 이다.

마찬가지 방식으로 d[a+1]부터 d[b] 까지는 모두 상쇄되고 d[a]만 1 증가시켜주고, d[b+1]만 1 감소시켜주면 된다.

 

 

구간의 인기도 구하기  

  d[]를 이용해서 c[x]를 구해보면, c[x] = d[1] + d[2] + ... + d[x] 이다.

(e.g. c[5] = d[1] + d[2] + d[3] + d[4] + d[5] = c[1] - 0 + c[2] - c[1] + c[3] - c[2] + c[4] - c[3] + c[5] - c[4] = c[5])

따라서 d[]에 대해 prefix sum을 구해주면(d[i] += d[i-1]) 이제 d[]에 있는 값이 c[] 에 해당하는 값들이다.

그리고 이 문제에서는 '[a, b] 구간의 인기도 합 / 구간의 수' 을 출력해줘야 하므로, [a, b] 구간의 인기도 합을 빠르게 구하기 위해 d[]에 다시 prefix sum을 구해준다. (d[i] += d[i-1])

 

  그럼 누적합 알고리즘을 통해 Q개의 각 query마다 O(1)에 답을 출력해줄 수 있다. ([a,b]구간의 인기도합 = d[b] - d[a-1])

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static final int SEC_OF_DAY = 24*60*60;

    private int timeTokenToSec(StringTokenizer st) {
        int h = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int s = Integer.parseInt(st.nextToken());
        s += h*3600;
        s += m*60;
        return s;
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        long[] arr = new long[SEC_OF_DAY+1];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " :-");
            int a = timeTokenToSec(st) + 1;
            int b = timeTokenToSec(st) + 1;
            arr[a]++;
            if (b+1 <= SEC_OF_DAY)
                arr[b+1]--;
            if (a > b)
                arr[1]++;
        }

        for (int i = 1; i <= SEC_OF_DAY; i++) {
            arr[i] += arr[i-1];
        }
        for (int i = 1; i <= SEC_OF_DAY; i++) {
            arr[i] += arr[i-1];
        }

        int q = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (q-->0) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " :-");
            int a = timeTokenToSec(st) + 1;
            int b = timeTokenToSec(st) + 1;
            if (a <= b) {
                long sum = arr[b] - arr[a - 1];
                sb.append(String.format("%.7f", 1d * sum / (b - a + 1))).append('\n');
            } else {
                long sum = arr[SEC_OF_DAY] - arr[a-1] + arr[b];
                sb.append(String.format("%.7f", 1d * sum / (SEC_OF_DAY - a + 1 + b))).append('\n');
            }
        }
        System.out.print(sb);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}