[JAVA] 백준 3985 : 롤케이크

문제

롤케이크를 L개로 잘랐고, N명의 사람들이 원하는 케이크 조각 번호를 적어 내면 순서대로 조각을 차지하게 된다. 이미 차지한 케이크는 갖지 못하고 그 조각을 제외한 부분만 받게 된다.

접근방법

1. 처음 사람들이 기대했던 케이크 양을 저장하고, 순서대로 케이크를 차지하게 한 다음, 실제 케이크를 차지한 결과를 확인한다.

2. 각각의 조각을 먹은 사람들의 인덱스가 저장되어 있는 케이크 배열 cake[], 처음 기대했던 케이크의 양을 가지고 있는 배열 people_before[], 실제로 차지한 케이크 양을 저장하는 people_after[] 배열 사용한다.

3. 각 케이크에 초기값 0이 아닌 수가 있으면 먹을 수 없으므로, 0일 때에만 값을 바꿔준다.

4. 최대 케이크 양이 아니라, 케이크를 차지한 사람을 알아야 하므로, max 값과 index 값을 함께 저장하며 for문을 돈다.

소스코드

public static void main(String[] args) throws IOException{
​
        Scanner sc = new Scanner(System.in);
        int L = sc.nextInt();
        int N = sc.nextInt();
        int[] cake = new int[L+1];           // 케이크 차지 현황
        int[] people_before = new int[N+1];  // 처음 기대했던 케이크 양
        int[] people_after = new int[N+1];   // 실제로 받은 케이크 양
​
        for(int i=1; i<=N; i++){
            int start = sc.nextInt();
            int end = sc.nextInt();
            // 기대하는 케이크 양 저장
            people_before[i] = end - start + 1;
​
            // 케이크 차지
            for(int j=start; j<=end; j++)
                if(cake[j] == 0)
                    cake[j] = i;
        }
​
        // 실제 받은 케이크 양 저장
        for(int i=1; i<=L; i++){
            if(cake[i] != 0)
                ++people_after[cake[i]];
        }
​
        // 기대, 실제 각각의 max 인덱스 계산
        int max_before = 0, index_before = 0;
        int max_after = 0, index_after = 0;
        for(int i=1; i<=N; i++){
            if(people_before[i] > max_before) {
                max_before = people_before[i];
                index_before = i;
            }
            if(people_after[i] > max_after) {
                max_after = people_after[i];
                index_after = i;
            }
        }
​
        System.out.println(index_before);
        System.out.println(index_after);
​
    }