페인트

import java.lang.*;
import java.util.*;


public class Main {
    public static final Scanner scanner = new Scanner(System.in);
    public static final int MAX_SEAT_NUMBER = 1000;
    public static final int MAX_COLOR_NUMBER = 100;

    /**
     *
     * @param n : 좌석의 수. 좌석은 0~(n-1)번의 번호를 가진다.
     * @param m : 좌석을 칠한 횟수.
     * @param paintings  : 좌석들을 색칠한 이벤트들의 정보
     */
    public static void solve(int n, int m, Painting[] paintings)
    {
        int[] seats = new int[n]; //seats[i] := i번 좌석의 최종 색상

        for(Painting painting : paintings){
            Arrays.fill(seats, painting.left, painting.right + 1, painting.color);
        }

        int[] table = new int[MAX_COLOR_NUMBER];
        for(int seat : seats){
            table[seat] ++;
        }

        int max_index = 0;
        int min_index = 0;
        int min_value = Integer.MAX_VALUE;
        for(int i = 0; i < 100; i ++){
            if(table[max_index] < table[i]){
                max_index = i;
            }
            if(table[i] != 0 && min_value > table[i]){
                min_index = i;
                min_value = table[i];
            }
        }
        System.out.println(max_index);
        System.out.println(min_index);
    }

    public static void main(String[] args) throws Exception {
        int n = scanner.nextInt();
        int m = scanner.nextInt();

        //paintings[i] := i번째에 일어난 색칠 이벤트의 정보
        Painting[] paintings = new Painting[m];


        for(int i = 0 ; i < m ; i ++)
        {
            //좌석의 번호는 1번부터 시작하므로, 0 ~ (n-1)범위로 맞추기 위하여 1씩 빼준다
            int left = scanner.nextInt()  -1;
            int right = scanner.nextInt() -1;
            int color = scanner.nextInt();
            paintings[i] = new Painting(left, right, color);
        }

        //문제의 정답을 구한다
        solve(n, m, paintings);
    }

}

//좌석들을 한 번 색칠하는 이벤트에 대한 정보
class Painting{
    public int left;
    public int right;
    public int color;
    Painting(int left, int right, int color)
    {
        this.left = left;
        this.right = right;
        this.color = color;
    }
}

풀이 해석

1. Painting 객체로 범위를 입력받는다.

2. 콘서트에 색칠한 범위를 Arrays.fill을 사용해서 처리해주었다. 

3. table[100] 배열을 통해 색칠한 색의 빈도 수를 계산해주었다.

4. 반복문을 통해 가장 많이 나온 색과, 적게 나온 색을 인덱스를 이용해서 구하였다.

- 따로 적게 나온 색을 min_index, min_value 해서 구한 이유는 처음 인덱스를 0으로 두고 풀면 

  빈도 수가 2 2 2 였다고 가정하면 첫번째 0번 인덱스를 통과해서 1번 인덱스가 가장 적게 나온 수로 구해진다.

- 정답은 0번 인덱스이므로 min_value 값을 Integer.MAX_VALUE를 통해 초기화해주었다. 

- 시간 복잡도는 O(N) + O(100) -> O(N) 시간으로 통과한다.