[프로그래머스-Lv2-JAVA] 광물 캐기
1. 문제
문제 캡처
이 문제는 광물을 채굴할 때 곡괭이 종류와 광물 종류 매칭에 따른 피로도 소모값이 매핑되어 있다. 모든 곡괭이는 사용 시 광물을 5번 캐야 하고, 캐야 하는 광물의 종류와 순서는 정해져 있다. 곡괭이 종류와 보유 개수들이 주어질 때 광물을 캘 수 있는 가장 작은 피로도를 찾는 문제이다.
2. 문제 분석
2.1. 문제 확인
이 문제는 마치 게임처럼 도구를 선택하여 광물을 캐는 느낌이 드는 문제이다. 보유 인벤토리에 사용할 수 있는 곡괭이 종류와 개수가 있고, 목표 지점에서 캘 수 있는 광물들이 순서대로 보여진다면, 플레이어 입장에서 가장 소모값이 작은 방법은 무엇인지 생각해 보자. 물론, 곡괭이는 소모 개념이 아니라 작업 지점마다 초기화된다고 가정해 보자.
곡괭이와 광물의 피로도 소모 관계는 아래와 같다.
위 표를 봤을 때 개발자의 의도는 광물과 곡괭이마다 등급이 있으며 곡괭이의 등급이 높을수록 높은 등급의 광물을 더 적은 피로도로 캘 수 있도록 설계한 것으로 보인다.
단순히 생각하면 각 광물 선택 시 광물 등급과 가장 근접하는 등급의 곡괭이를 사용하면 될 것으로 보인다.
하지만 이는 큰 오류가 있다. 현재 상태에서 최선이라고 생각하는 곡괭이 선택이라도 이후 나올 광물 종류에 따라 최선이 되지 않을 수 있다. 만약 다음과 같은 상태에서 시작한다고 가정해 보자.
| 보유 곡괭이 | 광물 순서 |
|---|---|
| 철 1, 돌 2 | 철 - 돌 - 다이아 |
예시 1 현재 상태에서 최소 피로도 기준으로 사용
| 사용 곡괭이 | 채굴 광물 | 소모 피로도 | 누적 소모 피로도 |
|---|---|---|---|
| 철 곡괭이 | 철 | 1 | 1 |
| 돌 곡괭이 | 돌 | 1 | 2 |
| 돌 곡괭이 | 다이아 | 25 | 27 |
예시 1에서는 철 광물을 캐야 할 때 현재 보유 중인 곡괭이에서 가장 효율적인 곡괭이 선택은 철 곡괭이이다. 현재 기준으로 철 곡괭이를 사용하면 철 광물을 캘 때는 피로도가 1이 소모된다. 하지만 이후 다이아 곡괭이를 캐야 할 때는 돌 곡괭이로 캐야 하기 때문에 25 피로도가 소모어 총 27의 피로도가 소모된다.
예시 2 미래 가치까지 판단하여 최소 누적 피로도 계산
| 사용 곡괭이 | 채굴 광물 | 소모 피로도 | 누적 소모 피로도 |
|---|---|---|---|
| 돌 곡괭이 | 철 | 5 | 5 |
| 돌 곡괭이 | 돌 | 1 | 6 |
| 철 곡괭이 | 다이아 | 5 | 11 |
미래 가치까지 판단한다면 처음에는 돌 곡괭이를 사용하여야 한다. 당장은 피로도 소모가 5로 철 곡괭이를 선택했을 때보다 더 크지만 이후 다이아 광물을 철 곡괭이로 캔다면 5의 피로도가 소모되어 두 개의 광물을 캐는데 10의 피로도가 소모된다. 총 피로도는 11로 예시 1번보다 누적 피로도 소모가 작다.
2.2. 해결 전략 구상
결국 이 문제는 현재 상태로만 최적화를 진행하는 국소적 최적화로 문제를 해결해 나간다면 전역적 최적화에 이르지 못한다. 이 말은 이전에 학습하였던 그리디 알고리즘은 적합하지 않다는 것을 의미한다.
학습했던 그리디 알고리즘으로는 해결이 어렵다. 그리고 최적화된 선택 방법으로 풀기 위해서는 조건을 찾는 것이 까다롭다. 왜냐하면 하나의 선택이 다른 선택에 영향을 주기 때문이다.
이 경우 생각할 수 있는 가장 간단한 방법은 모든 선택을 시도해서 결과적으로 가장 작은 피로도의 결과를 찾는 것이 될 것이다.
2.3. 타당성 검증
모든 선택을 시도하는 방법은 최적의 조건을 찾아 문제를 푸는 것보다 효율적이지 않지만 문제의 범위가 크지 않은 경우 충분히 유용할 것이다. 문제의 크기를 확인해 보면 아래와 같다.
곡괭이 종류 = 3, 각 종류별 곡괭이의 개수 <= 5, 광물의 길이 <= 50
이 문제는 곡괭이 하나당 반드시 5번의 광물을 캐야 한다. 광물 개수는 최대 50개이기 때문에 각 곡괭이 선택 시도는 최대 10회씩 이루어질 것이다. 이 기준으로 최대 경우의 수를 생각해 보자.
동일한 곡괭이는 구분이 불필요하다. 그렇기 때문에 각 종류별 곡괭이는 몇 개를 사용하는지만 결정하면 되는 조합의 개념이다. 하지만 최소 피로도를 구하기 위해서는 이 조합들의 순서 배치가 중요하므로 순열을 구해야 한다고 볼 수 있다. 그렇다면 결론적으로 조합에 대한 순열의 수이고, 각 조합마다 최대 사용 길이는 5로 제한된 수일 것이다.
이는 3종류에 대한 길이 10의 중복 순열의 수에서 1종류마다 6개 이상이 넘어가는 수를 제외해야 하므로 계산이 복잡하다. 하지만 지금 과정은 이 문제를 모든 선택 시도 시 컴퓨터가 해결할 수 있는 크기인지 확인하는 것이다. 그렇게 때문에 6개 이상을 제외하는 과정을 없앤다면 단순히 곡괭이 3종류에 대한 중복 순열의 값은 3^10, 즉 59,049가 된다.
6개 이상을 제외한 수는 59,049보다 반드시 작기 때문에 이 문제 최대 범위에서의 최악의 경우의 수는 59,049보다 작다. 그리고 광물을 캐는 길이는 1부터 10까지(0은 제외)이기 때문에 다른 모든 계산을 생략하고 단순히 *10을 한다고 해도 594,490이고 실제로는 이 값보다 지수적으로 작을 것이다.
결론이 나왔다. 이 문제를 모든 선택을 고려한 경우의 수는 594,490보다 반드시 작고 594,490번의 연산은 현대의 컴퓨터는 아주 빠르게 구할 수 있다. 이는 이 문제를 모든 선택을 시도한 횟수로 풀 수 있다는 의미가 된다.
모든 선택을 시도하여 최소 피로도를 코드로 구해보자.
3. 문제 해결
3.1. 첫 번째 코드 작성
import java.util.*;
class Solution {
public int solution(int[] picks, String[] minerals) {
// 곡괭이 등급별 점수 매핑 (0: 다이아, 1: 철, 2: 돌)
Map<Integer, Integer> picksPointMap = new HashMap<>(
Map.of(0, 25, 1, 5, 2, 1) // 다이아: 25, 철: 5, 돌: 1
);
// 광물 등급별 점수 매핑
Map<String, Integer> mineralPointMap = new HashMap<>(
Map.of("diamond", 25, "iron", 5, "stone", 1) // 다이아몬드: 25, 철: 5, 돌: 1
);
// 곡괭이로 채굴 가능한 최대 광물 수 계산
int maxCanMine = (picks[0] + picks[1] + picks[2]) * 5; // 곡괭이 개수 * 5
int realLen = Math.min(minerals.length, maxCanMine); // 실제로 채굴 가능한 광물 개수
// 광물을 5개 단위로 나누어 세트 구성
List<String[]> mineralSetList = new ArrayList<>();
for (int start = 0; start < realLen; start += 5) {
int end = Math.min(start + 5, realLen);
String[] mineralSet = Arrays.copyOfRange(minerals, start, end);
mineralSetList.add(mineralSet);
}
int mineralSetCount = mineralSetList.size(); // 실제 광물 세트 개수
// 곡괭이 선택에 대한 모든 순열을 저장할 리스트 초기화
List<List<Integer>> allSequences = new ArrayList<>();
allSequences.add(new ArrayList<>());
// 각 광물 세트에 대해 곡괭이 선택 순열 구성
for (int i = 0; i < mineralSetCount; i++) {
List<List<Integer>> tempSequences = new ArrayList<>();
for (List<Integer> sequence : allSequences) {
// 다이아 곡괭이 추가
List<Integer> diaSequence = new ArrayList<>(sequence);
diaSequence.add(0); // 다이아 곡괭이 선택
tempSequences.add(diaSequence);
// 철 곡괭이 추가
List<Integer> ironSequence = new ArrayList<>(sequence);
ironSequence.add(1); // 철 곡괭이 선택
tempSequences.add(ironSequence);
// 돌 곡괭이 추가
List<Integer> stoneSequence = new ArrayList<>(sequence);
stoneSequence.add(2); // 돌 곡괭이 선택
tempSequences.add(stoneSequence);
}
allSequences = tempSequences; // 순열 업데이트
}
// 최소 누적 피로도를 저장할 변수 초기화
int minFatigue = Integer.MAX_VALUE;
// 생성된 모든 곡괭이 선택 순열에 대해 피로도 계산
for (List<Integer> sequence : allSequences) {
int[] pickaxeUsed = new int[3]; // 각 곡괭이 타입별 사용 횟수 [다이아, 철, 돌]
// 각 순서에서 곡괭이 사용 횟수 계산
for (int pickType : sequence) {
pickaxeUsed[pickType]++;
}
// 사용된 곡괭이 수가 보유한 곡괭이 수를 초과하면 해당 순서는 무시
if (pickaxeUsed[0] > picks[0] || pickaxeUsed[1] > picks[1] || pickaxeUsed[2] > picks[2]) {
continue;
}
// 현재 순서에 대한 피로도 계산
int totalFatigue = 0; // 누적 피로도
boolean exceeded = false; // 최소 누적 피로도를 초과했는지 확인용 플래그
for (int i = 0; i < mineralSetCount; i++) {
int pickType = sequence.get(i); // 현재 세트에 사용된 곡괭이 타입
String[] mineralSet = mineralSetList.get(i); // 현재 광물 세트
for (String mineral : mineralSet) {
int mineralPoint = mineralPointMap.get(mineral); // 광물의 점수
int pickPoint = picksPointMap.get(pickType); // 곡괭이의 점수
// 피로도 계산 후 누적
totalFatigue += Math.max(mineralPoint / pickPoint, 1);
// 최소 피로도를 초과 여부 확인
if (totalFatigue >= minFatigue) {
exceeded = true;
break;
}
}
if (exceeded) break; // 최소 누적 피로도 초과 시 중지
}
// 현재 누적 피로도가 최소 누적 피로도보다 작으면 갱신
if (totalFatigue < minFatigue) {
minFatigue = totalFatigue;
}
}
// 최소 누적 피로도 반환
return minFatigue;
}
}위 코드의 흐름은 아래와 같다.
- 광물을 곡괭이로 캘 수 있는 단위인 5개씩 세트로 구성
- 광물 세트 리스트의 광물 세트마다 곡괭이 선택 순열 생성
- 순열 생성은 곡괭이 3 종류에 대해 모든 분기를 추가하는 형태로 생성 (제곱으로 추가)
- 광물 세트 리스트를 순회하며 광물 세트마다 곡괭이에 대한 피로도 계산 후 누적
- 최소 누적 피로도를 갱신하며 모든 광물 세트 리스트를 순회하면 최소 누적 피로도 반환
4.1. 코드의 문제점
코드를 프로그래머스에 제출하고 테스트는 통과하는 코드가 완성되었다. 하지만 테스트가 통과되었어도 전혀 만족스럽지 않았다. 이유는 작성한 코드가 불만족스럽기 때문이었다.
문제는 코드를 작성할 때 조합에 대한 순열 생성이었다. 원래 의도는 조합에 대한 순열을 순서대로 바로 확인하며 최소 피로도 갱신 가능성이 없을 시 바로 다음 탐색으로 넘어가고 싶었지만, 반복문으로 탐색 시 순열을 미리 생성해두지 않고 탐색하는 것에 대한 아이디어가 떠오르지가 않았다. 결국 모든 조합에 대한 순열을 먼저 초기화하고 해당 순열을 순회하여 누적 피로도를 계산하였고, 결론적으로는 여러 가지 부분에서 불만족스러운 코드가 작성되었다.
코드에서 불만족스러운 부분은 아래와 같다.
- 불필요한 순열도 생성하여 무조건 탐색해야 함.
- 탐색 시 불필요한 탐색을 건너뛰기 위해 곡괭이 사용 가능 수가 초과 됐는지 여부로 확인하여 가독성이 낮은 코드가 작성됨 -> 첫 의도는 곡괭이 보유 수량으로 관리하여 0에 도달 시 다른 곡괭이 선택을 의도함.
- 순열 생성에 대한 조합 구분을 별도의 ArrayList 객체로 관리하여 메모리 사용량이 높음.
- 광물을 미리 곡괭이 채굴 단위인 5개 단위로 구성해놓아야 함.
-> 결론적으로 코드 개선 필요성을 강하게 느끼고, 현재 문제 해결에 사용한 개념에 해당하는 정석적인 알고리즘이 있다면 찾아보기로 하였다.
4.1. 완전 탐색
이 문제에서 모든 시도를 선택하기 위한 방법을 알고리즘상으로는 완전 탐색이라고 부르며 완전 탐색 종류는 여러 종류가 있다는 것을 알게 되었다. 완전 탐색에 대한 정리는 추후 알고리즘 카테고리에서 정리해 보기로 하며 문제 개선을 위한 알고리즘은 DFS(깊이 우선 탐색)를 이용하기로 결정하였다.
4.2. 개선 코드 (DFS 사용)
class Solution {
// 최소 피로도 확인용 전역 변수
static int minimumFatigue = Integer.MAX_VALUE;
static Map<Integer, Integer> picksPointMap = new HashMap<>(
Map.of(0, 25, 1, 5, 2, 1) // 0: 다이아, 1: 철, 2: 돌
);
static Map<String, Integer> mineralPointMap = new HashMap<>(
Map.of("diamond", 25, "iron", 5, "stone", 1)
);
public int solution(int[] picks, String[] minerals) {
// 깊이 우선 탐색 호출
dfs(0, 0, picks, minerals);
// 탐색 완료 후 최소 피로도 반환
return minimumFatigue;
}
// DFS(깊이 우선 탐색), 재귀적으로 조합에 대한 순열을 확인
private void dfs(int nowIndex, int nowFatigue, int[] picks,
String[] minerals) {
// 현재 누적 피로도가 최소 누적 피로도보다 같거나 크다면 탐색 조기 종료
if (nowFatigue >= minimumFatigue) {
return;
}
// 모든 곡괭이를 사용했거나 광물을 모두 채굴하였다면 결과 반환
if (picks[0] == 0 && picks[1] == 0 && picks[2] == 0 || nowIndex >= minerals.length) {
// 조건을 만족했다면 현재 피로도가 최소 누적 피로도이므로 갱신
minimumFatigue = nowFatigue;
return;
}
// 백트래킹을 위한 상태 백업
int originalIndex = nowIndex;
int originalFatigue = nowFatigue;
// 곡괭이 선택
nextPick:
for (int i = 0; i < picks.length; i++) {
if (picks[i] <= 0) continue; // 현재 등급 곡괭이가 남아있지 않으면 다른 곡괭이 선택
picks[i]--; // 현재 곡괭이 사용
// 선택한 곡괭이로 최대 5개의 광물을 채굴
for (int j = 0; j < 5; j++) {
// 광물 배열의 끝에 도달한 경우
if (nowIndex >= minerals.length) {
// 최소 피로도 갱신 시도
minimumFatigue = Math.min(nowFatigue, minimumFatigue);
// 상태 복원 후 다음 곡괭이로 넘어감
picks[i]++;
nowIndex = originalIndex;
nowFatigue = originalFatigue;
continue nextPick; // 다음 곡괭이 선택
}
// 현재 광물을 채굴하며 피로도 계산
nowFatigue += Math.max(
mineralPointMap.get(minerals[nowIndex]) / picksPointMap.get(i), 1
);
nowIndex++; // 다음 광물로 이동
}
// DFS 재귀 호출로 다음 순열 인덱스 탐색
dfs(nowIndex, nowFatigue, picks, minerals);
// 상태 복원 (백트래킹)
picks[i]++;
nowIndex = originalIndex;
nowFatigue = originalFatigue;
}
}
}위 코드의 흐름은 아래와 같다.
- 깊이 우선 탐색 진행, 순차적으로 곡괭이 선택
- 광물 5개를 순회하며 피로도 갱신, 광물을 모두 캤다면 조기 종료 최소 누적 피로도 갱신 시도
- 다음 곡괭이 선택을 재귀적으로 호출, 매개변수로는 현재 채굴 중인 광물 번호와 피로도, 곡괭이 사용 상태를 전달
- 더 이상 탐색할 수 없을 시 이전 탐색으로 돌아간 후 상태 복구(백트래킹) 후 다른 경로 탐색
- 모든 탐색 완료 후 갱신된 최소 피로도 반환
5. 회고
문제 자체는 마치 게임처럼 이해하기 쉬운 구성으로 되어있기 때문에 금방 이해할 수 있었다. 그리디 알고리즘 학습 시 국소적 최적화와 전역적 최적화를 학습했기 때문에 그리디 알고리즘으로 풀기 힘든 문제라는 것을 알 수 있었고 최적화 로직을 생각하던 중 모든 선택을 시도하는 전략으로 해결 포인트를 잡았다.
하지만 문제를 해결하는 과정에서 불만족스러운 코드가 작성되었고, 테스트 자체는 통과하였으나 코드 개선이 필요하여 완전 탐색에 대한 알고리즘 학습 후 코드를 개선하였다. 이 문제도 먼저 완전 탐색(모든 곡괭이 선택) 개념으로 시도한 후 완전 탐색 알고리즘인 DFS를 학습하였기 때문에 DFS의 목적이 분명하게 느껴졌고, 백트래킹에 대한 개념이 굉장히 효율적이라고 느꼈다. 정석적인 알고리즘은 특정 문제 해결 시도에 대한 정답처럼도 느껴질 정도로 효율적이라는 생각이 들었다.
DFS로 코드를 개선하고 난 후 알고리즘 학습에 대한 동기가 분명해졌다. 단지 알고리즘의 개념 정도만 학습한 후 코드를 작성해도 코드의 품질 자체가 큰 차이가 나는 것이 느껴졌기 때문이다. 특히 원래 시도하려고 했던 의도와 동일하게 구현가능하게 만들어 준 것이 크게 만족스러웠다. 혼자서 생각해서 아이디어를 떠올리는 것에 막혀 문제 해결 의도와 다르게 다른 방법으로 우회해야 했던 경우 굉장히 답답한 마음이 들고 불편한 느낌을 받았지만 알고리즘의 배경지식은 구현 의도와 일치하는 코드를 효율적으로 작성하는 것에 도움이 될 것이 틀림없다.
결과적으로 느끼는 점은 혼자서 생각했다면 이런 아이디어까지 도달하는 데 많은 사고의 과정이 필요했을 것이고, 어쩌면 더 비효율적인 알고리즘을 구상하고 그에 만족했을지도 모른다. 하지만 현대의 많이 사용되는 알고리즘은 수많은 사고와 개선을 바탕으로 완성되어 왔을 것이기 때문에 알고리즘 학습은 나의 생각을 넓히는데도 분명한 역할을 할 것이다. 과장하여 표현한다면 프로그래밍상으로 접해지는 문제는 이미 수많은 천재들도 겪었을 것이며 그들의 어깨 위에 올라타 문제를 같이 푸는 것이 아닐까 하는 즐거운 상상도 해본다.
'알고리즘 풀이 기록 > 프로그래머스' 카테고리의 다른 글
| [프로그래머스-Lv2-JAVA] 아날로그 시계 (2) | 2025.01.14 |
|---|---|
| [프로그래머스-Lv2-JAVA] 요격 시스템 (0) | 2024.12.10 |
| [프로그래머스-Lv1-JAVA] 신고 결과 받기 (0) | 2024.12.03 |
| [프로그래머스-Lv1-JAVA] 성격 유형 검사하기 (1) | 2024.11.27 |
| [프로그래머스-Lv1-JAVA] 달리기 경주 (0) | 2024.11.24 |
