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) 시간으로 통과한다.
'자료구조 & 알고리즘 관련 > 코딩테스트' 카테고리의 다른 글
과유불급 (누적합) (0) | 2022.12.15 |
---|---|
색종이 (0) | 2022.12.14 |
피보나치 나머지 (0) | 2022.12.13 |
응모 (0) | 2022.12.13 |
3A-전화번호 (0) | 2022.12.12 |