[Java] 페인트 알고리즘

목차

1. 문제 설명
2. 알고리즘 접근방법
3. 소스코드

1. 문제 설명

하나의 연속된 데이터에 페인트를 칠한다
이 때 가장 많은 좌석이 가진 색과, 가장 적은 좌석이 가진 색의 번호를 찾아보자
단, 첫자리는 무조건 흰색(색 번호 : 0)이고 남는 칠해져있지 않는 자리는 제외한다
색번호의 종류로는 0 ~ 99가 있다

입력 형식

첫 줄에는 좌석의 수 N과 색칠을 할 방법의 수 M이 차례로 주어진다. N과 M은 모두 1,000 이하의 자연수
이후 M줄에 걸쳐서 공백으로 구분된 세 정수가 주어진다. 모든 규칙은 수행되는 순서대로 주어진다. 즉, 먼저 입력된 색칠 규칙이 먼저 적용된다.

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

출력 형식

첫 번째 줄에 가장 많은 좌석이 칠해진 색의 번호를 출력한다.
두 번째 줄에 가장 적은 좌석이 칠해진 색의 번호를 출력한다.
조건을 만족하는 색이 두 개 이상이라면 번호가 작은 색을 출력한다.

간단하게 문제 설명하면 위와 같이 색을 칠해
가장많은 좌석과 가장 적은좌석의 색 번호를 출력하면 된다
단 하나의 데이터가 두개의 색번호를 가질 수 없다
위 그림과 같이 이후에 색칠한 수가 덧칠해지게 된다

2. 알고리즘 접근 방법

• 좌석들을 색칠하는 정보를 클래스로 정의한다
  (즉, 2, 3번째 입력값 정보가 클래스로 정의)
• 실제로 좌석들을 색칠할 것은 아니고,
  배열의 원소의 값을 색상으로 추상화하여 이를 구현(seats[])
• 빈도 수를 구하는 방법은 모든 색상(0 ~ 99)에 대한
  빈도수 테이블(table[])을 만들어 값을 도출한다

3. 소스코드

import java.io.*;
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 p : paintings){
			// p := 모든 paintings의 원소가 차례로 한 번씩
			// seats[left] ~ seats[right] 까지 전부 색상 c로 덮어쓰자(색은 섞이지 않는다)
			for(int i = p.left; i <= p.right; i++){
				// seats[i] := seats[left] ~ seats[right]
				seats[i] = p.color;
			}
		}
		
		int[] table; // table[c] := 색상 c가 seats내에서 등장한 횟수
		table = new int[100]; 
		
		for(int i = 0; i < n; i++){
			table[seats[i]]++; // 모든 색상에 대한 빈도수 테이블 생성
		}
		
		// 1번째 조건 := 1번도 등장하지 않은 색상은 초기화 x(빈 색상)
		// 2번째 조건 := 같은 조건이면 색상 값의 번호가 작은애를 우선
		int minColor = -1; //가장 적게 등장한 색상
		int maxColor = -1; //가장 많이 등장한 색상

		for(int color = 0; color <= 99; color++){
			// color := 0 ~ 99 사이 모든 색상
			if(table[color] == 0) continue; // 한번도 등장하지 않은 색상은 건너뛴다
			
			if(minColor == -1 || table[color] < table[minColor]){
				minColor = color;
			}
			
			if(maxColor == -1 || table[color] > table[maxColor]){
				maxColor = color;
			}
		}
		
		System.out.println(maxColor);
		System.out.println(minColor);
	}

	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;
	}
}