4회차 - 알고리즘 기록 : 페인트

📌 페인트

  한 아이돌 그룹은 2집 앨범 발매 기념 콘서트를 열기로 하였다.

이 콘서트의 기획을 맞게 된 당신은 2집 앨범의 컨셉트에 맞게 콘서트장을 알록달록하게 꾸미고자 한다.

하지만 디자인 감각이 전혀 없던 당신은 어떻게하면 예쁘고 불규칙적으로 알록달록하게 색상을 배치할 수 있을지 고민을 하고있다.

당신은 콘서트장에 한 줄로 배치 된 좌석들 중 연속된 몇 칸을 골라 한 가지 색으로 색칠하고,

또 다른 연속된 몇 칸을 골라 색칠하는 과정을 반복하기로 하였다.

 처음에 모든 좌석은 하얀색(0번 색상)으로 색칠되어 있으며, 당신은 연속 된 몇 칸의 좌석을 골라서 한 가지 색으로 칠할 수 있다.  당신은 0번부터 99번까지 총 100가지 색상을 사용할 수 있다. 0번은 항상 흰색이라고 가정한다. 그러므로 가장 처음에 모든 좌석은 0번 색상으로 색칠되어 있다. 색깔과 색칠할 연속 된 좌석들을 선택하면 해당 좌석들은 모두 같은 색으로 칠해진다. 의자를 칠하는 페인트들은 순식간에 마르므로 두 가지 이상의 색상이 섞이는 일은 벌어지지 않는다.

 

 예를 들어서 좌석이 1번부터 10번까지 있다고 하자.  2번부터 5번까지의 좌석을 빨간색으로 색칠하고, 그 후 4번부터 7번까지의 좌석을 파란색으로 색칠하면 결과적으로 2~3번 좌석은 빨간색, 4~7번 좌석은 파란색이 된다. 그리고 나머지 좌석들은 흰색이 된다. 

 

 당신은 이렇게 불규칙적으로 좌석들을 색칠한 후, 가장 많은 좌석이 가진 색과 반대로 가장 적은 좌석이 가진 색의 번호를 찾고자 한다. 단, 마지막에 아무 좌석에도 칠해져 있지 않은 색상은 제외한다. 두 색의 번호를 찾을 수 있는 프로그램을 작성해보자.

 

입력 형식

 첫 줄에는 좌석의 수 N과 색칠을 할 방법의 수 M이 차례로 주어진다. N과 M은 모두 1,000 이하의 자연수이다.

이후 M줄에 걸쳐서 공백으로 구분된 세 정수가 주어진다. 모든 규칙은 수행되는 순서대로 주어진다. 즉, 먼저 입력된 색칠 규칙이 먼저 적용된다.

• 첫 번째 숫자는 색칠할 가장 왼쪽(번호가 작은) 좌석의 번호이다. 
• 두 번째 숫자는 색칠할 가장 오른쪽(번호가 큰) 좌석의 번호이다.
• 세 번째 숫자는 좌석에 칠할 색깔의 번호이다.

 

단, 좌석의 번호는 1과 N사이의 자연수이며. 색깔의 번호는 0이상 99이하의 정수이다.

 

출력 형식

 첫 번째 줄에 가장 많은 좌석이 칠해진 색의 번호를 출력한다.

  두 번째 줄에 가장 적은 좌석이 칠해진 색의 번호를 출력한다.

  조건을 만족하는 색이 두 개 이상이라면 번호가 작은 색을 출력한다.

 

예시

- 입력

10 2

2 5 1

4 7 2

 

- 출력

0

1

 

- 입력 1

10 2

1 9 5

2 10 5

 

- 출력 1

5

5

 

코드 풀이

/**
 *
 * @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 p : paintings ){
        // p 는 모든 paintings 의 원소가 차례로 한번씩
        // seats[left] ~ seats[rigth] 까지 전부 색상 c로 덮어쓰자.

        for( int i = p.left; i <= p.right; i++ ){
            seats[i] = p.color;
        }
    }

    int[] table = new int[100];
    for( int i = 0; i < n; i++ ){
        table[ seats[i] ] += 1;
    }

    // 1번도 등장하지 않은 색상은 초기화 x
    // 좋은 조건이면 색상 값이 번호가 작은 색 선택
    int minColor = -1; //가장 적게 등장한 색상
    int maxColor = -1; //가장 많이 등장한 색상

    for( int color = 0; color <= 99; color++ ){
        if(table[color] == 0){
            continue;
        }

        if(minColor == -1 || table[color] < table[minColor]){
            minColor = color;
        }

        if(minColor == -1 || table[color] > table[maxColor]){
            maxColor = color;
        }

    }

    System.out.println(maxColor);
    System.out.println(minColor);
}