[백준] 23295번: 스터디 시간 정하기1 Java/ 누적합, imos 이모스 풀이

https://www.acmicpc.net/problem/23295

문제

참가자들이 스터디에 참여할 수 있는 시간들을 입력받아 시간 만족도가 최대인 시간을 찾아 출력한다. 시간 만족도가 최대인 시간이 여러 개라면 시작 시간이 가장 빠른 시간을 출력한다.

 

 

풀이과정

1. 참가자별로 스터디에 참여하는 시간대를 입력 받아서 이모스배열과 누적합 배열을 만든다

2. 참가자가 입력한 시간중 가장 큰 값을 기준으로 반복문을 돌며 스터디시간 T의 구간합을 구하면서, 가장 큰 값이 나오면 해당 구간합의 인덱스 값을 갱신해준다 

이때 구간합 맥스값이 동일하면 인덱스가 작은 것으로 유지 -> (시간 만족도가 최대인 시간이 여러 개라면 시작 시간이 가장 빠른 시간을 출력한다.)

 

 

 

풀이코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer sto = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(sto.nextToken()); // 참가자 수
        int T = Integer.parseInt(sto.nextToken()); // 찾아야 할 시간
        int[] studyTime = new int[100001];
        int lastTm = 0;

        for (int i = 0; i < N; i++) {
            int enterCnt = Integer.parseInt(br.readLine());
            for (int y = 0; y < enterCnt; y++) {
                StringTokenizer sto2 = new StringTokenizer(br.readLine());
                int str = Integer.parseInt(sto2.nextToken());
                int end = Integer.parseInt(sto2.nextToken());

                lastTm = Math.max(lastTm, end);
                studyTime[str]++;
                if (end < studyTime.length) {
                    studyTime[end]--;
                }
            }
        }

        // 이모스배열, 누적합배열 만들기
        int[] prefixSum = new int[studyTime.length];
        prefixSum[0] = studyTime[0];
        for (int i = 1; i <= lastTm; i++) {
            studyTime[i] += studyTime[i - 1]; // 이모스배열
            prefixSum[i] = prefixSum[i - 1] + studyTime[i]; // 누적합배열
        }

        // 0번째 값으로 세팅
        int maxPrefixSum = prefixSum[T-1];
        int minStartIdx = 0;
        int minEndIdx = T;

        // 제일 참여자 많은 T시간대 구하기
        for (int i = 1; i < lastTm + 1; i++) {
            // 맥스값 갱신될때 해당 구간의 시작, 맥스값 갱신해주기 (시작값이 min인지 확인하고 갱신)
            if (i+T-1 > lastTm) break;
            int rangeSum = prefixSum[i + T-1] - prefixSum[i - 1] ;
            if (maxPrefixSum < rangeSum) {
                maxPrefixSum = rangeSum;
                minStartIdx = i;
                minEndIdx = i + T;
            }
        }

        sb.append(minStartIdx).append(" ").append(minEndIdx);
        bw.write(sb.toString());
        bw.flush();
        bw.close();

    }
}