[백준 20311] 화학 실험 - JAVA

문제 링크 : https://www.acmicpc.net/problem/20311

문제 정의

입력

• 시험관 개수 $N$
• 시험관에 들은 시약의 색깔 수 $K$
• 각 시약 색깔별 시험관 개수 배열 $c$

출력

• 옆 시험관의 시약 색깔과 같지 않도록 배열
  • 시험관의 색깔 번호를 공백으로 구분하여 순서대로 출력 (답 아무거나 출력)
  • 조건을 만족하는 시험관 배열을 만들 수 없으면 $-1$을 출력

---

접근 방법

가장 먼저 생각할 것은
가장 많은 개수를 차지하는 시약 색의 시험관 수가 번갈아 놓을 수 있는지 판별해야 합니다.

if (c[0].count * (long)2 > N + 1) return false;

해당 코드로 시험관의 수가 홀수나 짝수 상관없이 판별할 수 있도록 구현했습니다.

그런 후 다음과 같은 생각이 필요합니다.

그러면 가장 많이 남은 색깔의 개수가 번갈아 놓을 수 있는 최대 개수 이하이면
항상 해가 성립할까?

네 항상 성립한다고 볼 수 있습니다.

예시

위와 같이 9개의 시험관에 빨강 5 파랑 3 초록 1이 존재한다고 가정하겠습니다.

빨강색이 c[0].count * (long)2 <= N + 1 조건이 성립하는지 보자면
5 * 2 <= 9 + 1 은 10 <= 10 이므로 조건을 성립합니다.

그럼 어떤 방식으로 넣어야 되나요?

저는 색깔 상관없이 짝수칸부터 차례대로 채우고
그 이후 색깔 채우는 인덱스가 시험관의 인덱스를 넘어가는 순간
홀수칸을 첫 번째부터 채워나갈 겁니다.

우선 빨간색부터 채워보겠습니다.

이렇게 채우고 다음 색깔인 파란색을 채우기 위해 인덱스를 옮겼지만
시험관의 범위 밖에 인덱스가 나갔습니다.

그러면 이번에는 홀수 첫 번째 칸부터 파란색을 채우는 겁니다.

파란색을 개수만큼 다 채우고 초록색을 채울 차례입니다.

초록색도 마저 개수만큼 마저 채워주면
조건이 성립하도록 시험관을 배치하게 됩니다.

즉 가장 많은 색깔이 번갈아 배치할 수 있는 개수만큼만 존재한다면
해당 명제는 항상 성립하는 것을 볼 수 있습니다.

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;


class Color implements Comparable<Color> {
	int index;
	int count;

	public Color (int index, int count) {
		this.index = index;
		this.count = count;
	}

	@Override
	public int compareTo (Color o) {
		return o.count - this.count;
	}
}

public class Main {
	static int N;
	static int K;
	static StringTokenizer st;
	static int[] arr;
	static Color[] c;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		c = new Color[K];

		st = new StringTokenizer(br.readLine());
		int index = 1;
		for (int i = 0; i < K; i++) {
			int count = Integer.parseInt(st.nextToken());
			c[i] = new Color(index, count);
			index++;
		}

		Arrays.sort(c);

		if (!isFillArray()) {
			sb.append(-1);
		}
		else {
			for (int i = 0; i < N; i++) {
				sb.append(arr[i]).append(" ");
			}
		}
		System.out.println(sb);
	}

	static boolean isFillArray() {
		if (c[0].count * (long)2 > N + 1) return false;

		int pIndex = 0;
		arr = new int[N];

		for (int i = 0; i < K; i++) {
			int insertCount = c[i].count;
			int insertIndex = c[i].index;

			while (insertCount-- > 0) {
				arr[pIndex] = insertIndex;
				pIndex += 2;
				if (pIndex >= N) {
					pIndex = 1;
				}
			}
		}
		return true;
	}
}