프로그래머스 | Level 2 | 광물 캐기

Programmers | Level 2 | 광물 캐기
Problems
- 📘 Src: Programmers
- 🗂️ Cat: Greedy
Description
마인은 곡괭이로 광산에서 광석을 캐려고 합니다. 마인은 다이아몬드 곡괭이, 철 곡괭이, 돌 곡괭이를 각각 0개에서 5개까지 가지고 있으며, 곡괭이로 광물을 캘 때는 피로도가 소모됩니다. 각 곡괭이로 광물을 캘 때의 피로도는 아래 표와 같습니다.
곡괭이 \ 광물 | 다이아몬드 | 철 | 돌 |
---|---|---|---|
다이아몬드 | 1 | 1 | 1 |
철 | 5 | 1 | 1 |
돌 | 25 | 5 | 1 |
예를 들어, 철 곡괭이는 다이아몬드를 캘 때 피로도 5가 소모되며, 철과 돌을 캘때는 피로도가 1씩 소모됩니다. 각 곡괭이는 종류에 상관없이 광물 5개를 캔 후에는 더 이상 사용할 수 없습니다.
마인은 다음과 같은 규칙을 지키면서 최소한의 피로도로 광물을 캐려고 합니다.
- 사용할 수 있는 곡괭이중 아무거나 하나를 선택해 광물을 캡니다.
- 한 번 사용하기 시작한 곡괭이는 사용할 수 없을 때까지 사용합니다.
- 광물은 주어진 순서대로만 캘 수 있습니다.
- 광산에 있는 모든 광물을 캐거나, 더 사용할 곡괭이가 없을 때까지 광물을 캡니다.
즉, 곡괭이를 하나 선택해서 광물 5개를 연속으로 캐고, 다음 곡괭이를 선택해서 광물 5개를 연속으로 캐는 과정을 반복하며, 더 사용할 곡괭이가 없거나 광산에 있는 모든 광물을 캘 때까지 과정을 반복하면 됩니다.
마인이 갖고 있는 곡괭이의 개수를 나타내는 정수 배열 picks
와 광물들의 순서를 나타내는 문자열 배열 minerals
가 매개변수로 주어질 때, 마인이 작업을 끝내기까지 필요한 최소한의 피로도를 return
하는 solution
함수를 완성해주세요.
Constraints
picks
는[dia, iron, stone]
과 같은 구조로 이루어져 있습니다.- 0 ≤ dia, iron, stone ≤ 5
- dia는 다이아몬드 곡괭이의 수를 의미합니다.
- iron은 철 곡괭이의 수를 의미합니다.
- stone은 돌 곡괭이의 수를 의미합니다.
- 곡괭이는 최소 1개 이상 가지고 있습니다.
- 5 ≤
minerals
의 길이 ≤ 50minerals
는 다음 3개의 문자열로 이루어져 있으며 각각의 의미는 다음과 같습니다.- diamond : 다이아몬드
- iron : 철
- stone : 돌
Examples
picks | minerals | result |
---|---|---|
[1, 3, 2] | ["diamond", "diamond", "diamond", "iron", "iron", "diamond", "iron", "stone"] | 12 |
[0, 1, 1] | ["diamond", "diamond", "diamond", "diamond", "diamond", "iron", "iron", "iron"] | 50 |
Solutions
Code
import java.util.*;
class Solution {
public int solution(int[] picks, String[] minerals) {
// 사용할 곡괭이의 총 개수
int n = sum(picks); // 곡괭이 개수의 합계를 구함
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> sum(b) - sum(a)); // 피로도가 높은 그룹을 우선으로 처리
// 광물을 5개씩 그룹화하여 피로도 배열 생성
for (int i = 0; i < n; i++) {
int start = i * 5;
List<Integer> group = new ArrayList<>();
for (int j = 0; j < 5; j++) {
int next = start + j;
if (next >= minerals.length) break; // 광물의 배열을 벗어나면 종료
String mineral = minerals[next];
if (mineral.equals("diamond")) group.add(25); // 다이아몬드: 피로도 25
if (mineral.equals("iron")) group.add(5); // 철: 피로도 5
if (mineral.equals("stone")) group.add(1); // 돌: 피로도 1
}
pq.offer(group.stream().mapToInt(Integer::intValue).toArray()); // 그룹을 큐에 저장
}
int result = 0; // 최소 피로도를 저장할 변수
// 곡괭이를 사용하여 그룹화된 광물 캐기
while (!pq.isEmpty()) {
int[] group = pq.poll(); // 가장 피로도가 큰 그룹부터 처리
if (picks[0] > 0) {
result += group.length; // 다이아몬드 곡괭이: 각 광물마다 피로도 1
picks[0]--;
} else if (picks[1] > 0) {
for (int num : group) {
result += num == 1 ? 1 : num / 5; // 철 곡괭이: 돌은 1, 다이아몬드는 5로 나누어 계산
}
picks[1]--;
} else {
result += sum(group); // 돌 곡괭이: 모든 광물의 피로도를 그대로 합산
picks[2]--;
}
}
return result;
}
// 배열의 총합을 구하는 보조 함수
private int sum(int[] numbers) {
int result = 0;
for (int number : numbers) {
result += number;
}
return result;
}
}
Approaches
이 문제는 주어진 곡괭이로 가능한 한 최소의 피로도로 광물을 캐는 그리디(Greedy) 알고리즘을 이용해 해결할 수 있습니다. 각 곡괭이의 특성을 고려하여 피로도가 높은 광물 그룹을 효율적으로 처리하는 것이 핵심입니다.
1. 문제 분석
이 문제는 주어진 곡괭이와 광물의 조합을 어떻게 활용해 최소한의 피로도로 모든 광물을 채굴할 수 있을지에 대한 전략을 수립하는 것이 핵심입니다. 마인은 다이아몬드, 철, 돌 곡괭이를 가지고 있으며, 각각의 곡괭이는 특정 광물을 캘 때 소모되는 피로도가 다릅니다. 예를 들어, 다이아몬드 곡괭이는 모든 광물을 피로도 1로 캘 수 있지만, 철 곡괭이는 다이아몬드를 캘 때 피로도 5, 돌 곡괭이는 피로도 25가 소모됩니다. 이처럼 곡괭이와 광물의 조합에 따라 피로도가 크게 달라지기 때문에 각 곡괭이의 특성을 파악하고, 이를 바탕으로 가장 효율적인 채굴 전략을 세우는 것이 중요합니다.
또한, 곡괭이의 사용은 일정한 규칙을 따라야 합니다. 한 번 선택한 곡괭이는 연속으로 5개의 광물을 캘 수 있는 사용 한도가 있으며, 이후 다른 곡괭이로 교체하여 새로운 5개의 광물을 캘 수 있습니다. 이로 인해 광물을 5개 단위로 그룹화하여 작업해야 하며, 각 그룹을 캘 때 사용할 곡괭이를 어떻게 선택할지가 문제 해결의 주요 요소입니다.
주어진 광물을 5개씩 그룹화한 후, 각 그룹에 대해 가장 적합한 곡괭이를 선택하여 최소 피로도로 작업을 완료해야 합니다. 이때, 각 그룹의 피로도가 높은 순서대로 곡괭이를 배정하는 것이 중요합니다. 왜냐하면, 피로도가 높은 광물 그룹에는 피로도 소모가 적은 다이아몬드 곡괭이를 배정하고, 상대적으로 피로도가 낮은 그룹에는 철 또는 돌 곡괭이를 사용하는 것이 전체 피로도를 최소화할 수 있는 전략이 되기 때문입니다.
이 문제는 곡괭이와 광물의 조합을 통해 최적의 피로도 계산을 목표로 하며, 광물 그룹의 피로도를 계산하고, 가장 피로도가 높은 그룹부터 효율적으로 곡괭이를 배치하는 과정을 통해 최소한의 피로도로 작업을 완료하는 방법을 찾는 것입니다.
2. 접근 방식
주어진 곡괭이는 각각 5개씩의 광물을 연속으로 캘 수 있는 사용 한도가 있으며, 곡괭이의 종류에 따라 같은 광물을 캘 때 소모되는 피로도가 달라지므로 이를 잘 고려하여 곡괭이를 배분해야 합니다.
- 광물 그룹화: 주어진 광물 배열을 5개씩 묶어서 피로도 배열을 생성합니다. 각 광물의 피로도는 곡괭이의 종류에 따라 다르게 적용되기 때문에, 이를 효과적으로 계산하기 위해 각 광물의 종류를 다이아몬드, 철, 돌로 구분하여 다이아몬드는 25, 철은 5, 돌은 1의 피로도를 할당합니다. 이렇게 하면, 각 그룹의 전체 피로도를 하나의 정수 값으로 계산할 수 있으므로 이후의 곡괭이 배정 과정에서 쉽게 비교할 수 있습니다.
- 피로도가 높은 그룹 우선 처리: 이렇게 계산된 그룹의 피로도를 우선순위 큐에 저장하여 내림차순으로 정렬합니다. 이렇게 하면 피로도가 가장 높은 그룹부터 차례대로 꺼내어 가장 효율적인 곡괭이를 우선 배정할 수 있습니다. 예를 들어, 다이아몬드 곡괭이는 모든 광물에 대해 피로도 1로 작업을 수행할 수 있기 때문에, 피로도가 높은 그룹에 우선적으로 배정하여 피로도 누적을 최소화할 수 있습니다.
- 곡괭이 선택 및 배치 전략: 각 그룹을 처리할 때 사용할 곡괭이를 결정하는 데 있어, 피로도가 높은 그룹부터 다이아몬드 곡괭이, 철 곡괭이, 돌 곡괭이 순으로 배정하여 전체 피로도를 최소화합니다. 이때, 곡괭이를 사용할 때마다 해당 곡괭이의 사용 가능 횟수가 하나씩 차감되며, 곡괭이가 모두 소진된 경우 더 이상 해당 종류의 곡괭이는 사용할 수 없습니다.
- 최종 결과 도출: 위의 과정이 끝난 후, 각 곡괭이로 작업한 모든 피로도를 합산하여 최소 피로도를 계산합니다. 사용 가능한 곡괭이가 없거나, 더 이상 처리할 그룹이 남아있지 않으면 작업을 중단하고, 지금까지의 누적 피로도를 반환하여 작업을 완료합니다.
이와 같은 과정을 통해, 주어진 곡괭이와 광물의 배치를 최적화하여 최소 피로도를 계산할 수 있습니다.
3. 광물 그룹화 및 우선순위 큐 활용
곡괭이의 총 개수를 picks
배열을 통해 계산하여, 이를 바탕으로 광물을 그룹화하는 작업을 수행합니다. 여기서 picks
는 각 곡괭이의 개수를 나타내는 배열로 [다이아몬드 곡괭이 수, 철 곡괭이 수, 돌 곡괭이 수]
형식으로 주어집니다. 모든 곡괭이의 총 개수를 계산한 후, 이를 기준으로 최대 몇 개의 광물 그룹을 만들 수 있는지 결정하게 됩니다.
광물은 주어진 순서대로 처리해야 하며, 곡괭이의 사용량에 따라 한 번에 5개씩 그룹화하여 각 그룹의 피로도를 계산합니다. 각 광물의 피로도는 다이아몬드, 철, 돌 순으로 각각 25, 5, 1로 설정합니다. 이렇게 만든 그룹을 우선순위 큐에 저장하여, 피로도가 높은 그룹부터 처리할 수 있도록 합니다.
// 사용할 곡괭이의 총 개수
int n = sum(picks); // picks 배열의 각 요소의 합계를 통해 총 곡괭이 수를 계산
// 피로도가 높은 그룹을 우선 처리하기 위한 우선순위 큐 (내림차순 정렬)
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> sum(b) - sum(a));
// 광물을 5개씩 그룹화하여 피로도 배열 생성
for (int i = 0; i < n; i++) {
int start = i * 5; // 각 그룹의 시작 인덱스
List<Integer> group = new ArrayList<>(); // 각 그룹의 피로도를 저장할 리스트
// 각 그룹 내 최대 5개의 광물을 포함
for (int j = 0; j < 5; j++) {
int next = start + j; // 그룹 내 인덱스 계산
if (next >= minerals.length) break; // 광물 배열을 벗어나면 중단
// 광물의 종류에 따라 피로도 값 설정
String mineral = minerals[next];
if (mineral.equals("diamond")) group.add(25); // 다이아몬드의 피로도는 25
if (mineral.equals("iron")) group.add(5); // 철의 피로도는 5
if (mineral.equals("stone")) group.add(1); // 돌의 피로도는 1
}
// 각 그룹의 피로도 배열을 큐에 저장
pq.offer(group.stream().mapToInt(Integer::intValue).toArray());
}
4. 최소 피로도 계산
이 단계에서는 우선순위 큐에서 각 광물 그룹을 꺼내어 사용할 수 있는 곡괭이를 선택하고, 최소한의 피로도로 그룹을 처리합니다. 곡괭이의 종류에 따라 광물을 캘 때의 피로도가 달라지기 때문에, 피로도가 큰 그룹부터 우선적으로 다이아몬드 곡괭이, 철 곡괭이, 돌 곡괭이 순으로 사용하여 피로도를 최소화해야 합니다.
곡괭이 사용 전략은 다음과 같은 순서로 진행됩니다:
- 우선순위 큐에서 그룹을 꺼내기: 우선순위 큐(Priority Queue)는 피로도가 높은 그룹이 가장 먼저 꺼내지도록 정렬되어 있습니다. 큐에서 가장 피로도가 높은 그룹을 꺼내어, 다이아몬드 곡괭이가 남아 있으면 곡괭이를 사용하여 그룹을 처리합니다. 다이아몬드 곡괭이는 모든 광물을 1의 피로도로 처리하기 때문에, 가능한 한 피로도가 높은 그룹을 우선적으로 처리하는 것이 중요합니다.
- 곡괭이 종류별 피로도 계산: 각 그룹의 광물을 캘 때 다이아몬드 곡괭이, 철 곡괭이, 돌 곡괭이 순으로 사용합니다.
- 곡괭이 소모 후 다음 그룹으로 이동: 곡괭이를 사용한 후에는 해당 곡괭이의 남은 개수를 줄이고, 다음 그룹으로 넘어갑니다. 만약 우선순위 큐에 더 이상 남은 그룹이 없다면, 작업을 종료합니다. 각 곡괭이의 수에 따라 그룹화가 이미 진행되었기 때문에, 남은 그룹의 수만 고려하여 반복을 끝낼 수 있습니다.
이 과정을 통해 각 그룹을 순차적으로 처리하면서 최적의 곡괭이 사용 전략을 통해 최소 피로도를 계산할 수 있습니다. 모든 그룹이 처리될 때까지 이 전략을 반복하여, 최종적으로 누적된 피로도를 구합니다.
// 곡괭이를 사용하여 그룹화된 광물 캐기
while (!pq.isEmpty()) {
int[] group = pq.poll(); // 가장 피로도가 큰 그룹부터 처리
if (picks[0] > 0) { // 다이아몬드 곡괭이: 모든 광물에 대한 피로도 +1
result += group.length;
picks[0]--;
} else if (picks[1] > 0) { // 철 곡괭이: 다이아몬드는 +5, 그 외 +1
for (int num : group) {
result += num == 1 ? 1 : num / 5;
}
picks[1]--;
} else { // 돌 곡괭이: 모든 광물의 피로도를 그대로 합산
result += sum(group);
picks[2]--;
}
}
5. 최소 피로도 도출
모든 그룹의 광물을 적절한 곡괭이로 처리한 후, 누적된 피로도를 최종 결과로 반환합니다. 이때, 각 그룹을 처리하는 과정에서 피로도를 최소화하도록 곡괭이를 선택했기 때문에, 누적된 값은 주어진 조건 내에서 최소한의 피로도로 광물을 채굴한 결과가 됩니다.
// 최소 피로도 반환
return result;
Complexity
- ⏳ TC: O(n log n)
- 💾 SC: O(n)
곡괭이 사용과 우선순위 큐를 통한 피로도 계산 과정에서 발생하는 시간 복잡도는 O(n log n)입니다. 각 그룹을 큐에 저장하고, 피로도가 높은 그룹을 먼저 처리할 때의 정렬 연산이 이에 해당합니다. 공간 복잡도는 그룹의 개수에 비례하여 O(n)입니다.
- Algorithm
- Greedy