“`
작성일: 2023년 10월 4일
문제 설명
당신은 해변에서 조약돌을 수집하는 일을 맡고 있습니다. 조약돌을 특정한 규칙에 따라 꺼내야 합니다.
조약돌의 색은 여러 가지이며, 조약돌이 있는 곳에는 N개의 조약돌이 리스트로 주어집니다.
이 리스트의 각 조약돌은 고유한 색깔을 가지고 있습니다.
당신은 두 가지 작업을 반복하여 수행할 수 있습니다:
1. 조약돌을 꺼내고
2. 조약돌을 다시 넣을 수 있습니다.
모든 조약돌을 다 꺼내려면, 최소 몇 번의 조작(꺼내기나 넣기)을 해야 할까요?
만일 모든 조약돌을 꺼낼 수 없는 경우, ‘Impossible’이라고 출력하세요.
입력형식
- 첫 번째 줄에는 조약돌의 수 N (1 ≤ N ≤ 100)이 주어집니다.
- 두 번째 줄에는 N개의 조약돌의 색깔이 주어집니다. 색깔은 1부터 100까지의 정수로 주어집니다.
출력형식
모든 조약돌을 다 꺼내려면 최소 몇 번의 조작이 필요한지 출력하세요. 불가능한 경우 ‘Impossible’로 출력합니다.
문제 분석
이 문제는 조약돌의 색 팔레트를 관리하고, 조작을 최소화하면서 처리를 진행해야 한다는 핵심을 내포하고 있습니다.
각 조약돌은 색에 따라 그룹으로 묶을 수 있으며, 이러한 그룹화는 원하는 조약돌을 꺼내는데 있어 중요한 역할을 합니다.
규칙을 바탕으로 조약돌의 꺼내기와 넣기를 전략적으로 조합함으로써 문제를 해결하는 접근 방식을 가질 필요가 있습니다.
접근 방식
문제를 효과적으로 해결하기 위해 우리는 다음과 같은 단계로 접근할 수 있습니다.
- 조약돌 색 빈도 계산: 각 색깔이 얼마나 많은 조약돌이 있는지 카운팅 합니다.
- 최소 조작 횟수 계산: 조약돌 수가 홀수인 경우, 항상 꺼내기 작업이 우선되어야 하며 최종적으로 나머지 작업을 추가적으로 고려해야 합니다.
- 유효성 검사: 모든 조약돌을 꺼낼 수 있는지 여부를 확인합니다.
샘플 코드
import java.util.HashMap;
import java.util.Scanner;
public class PebbleRemoval {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
HashMap colorFrequency = new HashMap<>();
for (int i = 0; i < N; i++) {
int color = scanner.nextInt();
colorFrequency.put(color, colorFrequency.getOrDefault(color, 0) + 1);
}
int operations = 0;
int oddCount = 0;
for (int freq : colorFrequency.values()) {
if (freq % 2 != 0) {
oddCount++;
}
operations += freq;
}
if (oddCount > 1) {
System.out.println("Impossible");
} else {
System.out.println(operations);
}
scanner.close();
}
}
코드 설명
위의 자바 코드는 조약돌 색의 빈도수를 카운트하기 위한 기본적인 구조를 보여줍니다.
HashMap을 사용하여 각 색깔의 빈도를 카운트합니다.- 모든 빈도를 검사하여 홀수인 경우를 체크하며, 꺼내기 작업을 추적합니다.
- 최종적으로 꺼내기 작업이 불가능한 경우 ‘Impossible’을 출력합니다.
“`