[필수 문제] 상자 꾸미기

1. 문제

면이 6개인 상자가 있다. 이를 여러 가지 색종이를 붙여 꾸밀려고 하는데, 단 조건이 있다. 인접한 면에 같은 색의 색종이를 붙이면 안 된다는 것이다. 또한, 한 면에는 한 장의 색종이만 붙일 수 있다. 여러 가지 색의 색종이들이 주어졌을 때, 조건을 만족하여 상자의 모든 면에 붙일 수 있는지 판별하는 프로그램을 작성하시오.

---

입력

첫째 줄에 색종이의 장수 N ( 1 <= N <= 1,000 ) 이 주어진다. 둘째 줄에 각각의 색종이의 색깔을 나타내는 N개의 숫자가 주어진다. 색깔은 양의 정수로 이루어져 있고, 1부터 N까지의 범위의 수이다.

출력

조건을 만족하면서 상자를 꾸밀 수 있으면 “YES”, 아니면 “NO”를 출력한다.

예제 입력

case 1)

6
1 2 1 2 1 3

 

case 2)

6
1 2 3 1 2 3

 

case 3)

7
1 1 1 2 2 3 3

 

case 4)
8
1 2 2 2 1 1 1 3

예제 출력

case 1) NO

case 2) YES

case 3) YES

case 4) NO

 

 

 

2. 풀이

이 문제는 직접 정육면체에 최소한의 색으로 칠해보아야 한다.

 

직접 확인해본다면, 총 3가지 색 2개씩으로 칠할 수 있음을 확인할 수 있다. 즉, 다음과 같은 조건을 만족해야한다.

• 총 색의 개수는 3개 이상
• 총 색종이 개수는 6개 이상

 

import java.io.*;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {

        int n = Integer.parseInt(br.readLine());

        int[] colors = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) colors[i] = Integer.parseInt(st.nextToken());

        // 각 색의 개수를 Map에 저장
        Map<Integer, Integer> map = new HashMap<>();
        for(int key : colors) map.put(key, map.getOrDefault(key, 0) + 1);

        int sum = 0;
        Iterator<Integer> iter = map.keySet().iterator();
        while(iter.hasNext()) {
            int key = iter.next();
            int value = map.get(key);

            if(value > 2) value = 2; // 색종이 개수가 2개 이상일 경우 2로 설정하여 계산
            sum += value;
        }

        if(sum >= 6) bw.write("YES");
        else bw.write("NO");

        br.close();
        bw.flush();
        bw.close();
    }

}