[알고리즘 문제] Box Painting

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int n = sc.nextInt(); // 색상의 갯수

int count = 0; // 칠해진 숫자 count

int[] colors = new int[1000]; // 색상의 빈도수를 체크

int num; // 입력받은 숫자

if (n < 6) { // 모든 면을 칠해야 함.

System.out.println("NO");

return;

}

for (int i = 0; i < n; i++) {

num = sc.nextInt();

if (colors[num] < 2) { // 1 1 1 의 경우 서로 마주보는 경우, 즉 한쌍의 경우만 필요

// 하기 때문에 색깔의 빈도수가 2초과인 경우는 제외

colors[num] += 1; // 색상을 한번 사용했으면 +1을 하여 사용했음을 체크

count++; // 체크했다는 것은 색상을 한번 칠했기 때문에 ++

} else {

continue;

}

}

if (count >= 6) { // 1 2 3 4 5 6 7 8 9의 경우 count는 6을 초과하기 때문에 6이상.

System.out.println("YES");

} else {

System.out.println("NO");

}

}

}

 이 문제는 코드가 길지는 않은데, 입력받은 숫자로 색상을 칠했을 떄 같은 색상이 서로 "인접"하지 않게 색칠하는 방법을 생각해내는게 좀 힘들었다. 

만약에 1 2 3 4 5 6이 입력된다면 그냥 막 칠해도 중복되는 숫자가 없으니 인접한 경우를 고려하지 않아도 되는데, 만약 1 2 2 2 1 1 1 3 같은 경우라면 결국에는 인접할 수 밖에 없게 된다.

아이디어는, 각 색상의 빈도수를 체크해서 만약 2를 넘어가는 경우는 count값(실제 박스에 칠해진 숫자의 개수)에서 제외하는 것이다. 

이유는 인접하지 않는 경우는 서로 마주보는 경우 밖에 없다. 그렇게 되면 숫자의 한쌍(2개)로만 존재하게 되고 추가적으로 이 숫자가 존재하면 사실 의미가 없기 떄문에, 칠할 수 없는 값이고 count++를 하지 않았다.

만약 모든 숫자가 서로 다른 값이라면 if (colors[num] < 2) 은 true가 되어서 모든 숫자의 빈도수가 1이 되고, count역시 입력받은 숫자만큼 ++될 것이다. 그래서 마지막 조건에 count의 범위를 count >= 6  로 설정하였다.