https://school.programmers.co.kr/learn/courses/30/lessons/172927
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
카페에서 문제 푸는데..
점심시간 이후 되니까.. 사람이 많아져서 굉장히 시끄럽다..🙉
노이즈 캔슬링이 되는 에어팟 맥스2가 필요하다🎧
예외 케이스를 놓쳐서 시간이 더 걸렸다.
[예외 케이스]: 5칸이 무조건 보장 되지 않음. 중간에 배열이 짤릴 수 있음!
와우 다른 사람 이 문제 푼거 보니까
어떤 사람은 BFS, DFS, 그리디.. 나만의 방식으로 한 사람은 없다 ㅋㅋㅋ
그런 점에서 좀 뿌듯
문제 이해
Flow
해결 코드
import java.util.ArrayList;
import java.util.List;
public class 광물캐기3_개선 {
public static void main(String[] args) {
Solution solution = new Solution();
int[] arr = {1, 3, 2};
String[] arr2 = {"diamond", "diamond", "diamond", "iron", "iron", "diamond", "iron", "stone"};
int result = solution.solution(arr, arr2);
System.out.println(result);//12
}
static class Solution {
public int solution(int[] picks, String[] minerals) {
int picksSum = picks[0] + picks[1] + picks[2];
if (picksSum <= 0) {
return 0;
}
int len = Math.min(minerals.length, picksSum * 5);
List<FiveMineralGroup> fiveMineralGroupsList = new ArrayList<>();
for (int i = 0; i < len; i += 5) {
int diamondCount = 0;
int partTotalPonit = 0;
int groupIndex = 0;
// minerals을 0~4, 5~9 이런식으로 5묶음으로 key: 총합, value: dimond
for (int j = 0; j < 5 && i + j < minerals.length; j++) {
// key: 총합, value: dimond 개수
if (minerals[i + j].equals("diamond")) {
diamondCount += 1;
partTotalPonit += 25;
} else {
partTotalPonit += (minerals[i + j].equals("iron")) ? 5 : 1;
}
groupIndex += 1;
}
// partTotalPonit가 같은 경우도 있을 수도? map -> List 변경
fiveMineralGroupsList.add(new FiveMineralGroup(partTotalPonit, diamondCount, groupIndex));
}
// partTotalPonit가 값이 큰 순서대로 정렬
fiveMineralGroupsList.sort((p1, p2) -> Integer.compare(p2.getTotalPoint(), p1.getTotalPoint()));
int result = 0;
int index = 0;
// 다이아몬드 도구 사용
for (int i = 0; i < picks[0] && index < fiveMineralGroupsList.size() && index < len; i++, index++) {
// [예외] 중간에 짤릴 수도 있음
int count = fiveMineralGroupsList.get(index).getGroupIndex();
result += count;
}
// 철 도구 사용
for (int i = 0; i < picks[1] && index < fiveMineralGroupsList.size() && index < len; i++, index++) {
FiveMineralGroup fiveMineralGroup = fiveMineralGroupsList.get(index);
int diamondCount = fiveMineralGroup.getDiamondCount();
// [예외] 중간에 짤릴 수도 있음
result += (diamondCount * 5) + (fiveMineralGroup.getGroupIndex() - diamondCount); // 철 도구로 채굴 시 점수 계산
}
// 돌 도구 사용
for (int i = 0; i < picks[2] && index < fiveMineralGroupsList.size() && index < len; i++, index++) {
result += fiveMineralGroupsList.get(index).getTotalPoint(); // 돌 도구로 채굴 시 점수 그대로 추가
}
return result;
}
class FiveMineralGroup {
private int totalPoint;
private int diamondCount;
private int groupIndex;
public FiveMineralGroup(int totalPoint, int diamondCount, int groupIndex) {
this.totalPoint = totalPoint;
this.diamondCount = diamondCount;
this.groupIndex = groupIndex;
}
private int getDiamondCount() {
return diamondCount;
}
private int getTotalPoint() {
return totalPoint;
}
public int getGroupIndex() {
return groupIndex;
}
}
}// Solution class end
}//class end
왜 이 방법이 그리디가 아닌가?
- 미리 정렬된 그룹 처리: 코드에서는 광물 그룹을 피로도가 높은 순서로 미리 정렬한 후에 곡괭이를 사용하는 순서를 정하고 있습니다. 그러나 Greedy 알고리즘에서는 주어진 순간에 어떤 그룹을 먼저 처리할지 결정하는 즉시적인 선택을 해야 합니다. 정렬 후에 처리하는 방식은 더 구조적인 접근이므로, 이 자체가 Greedy 접근법이라고 할 수 없습니다.
- 모든 그룹을 고려: Greedy 알고리즘에서는 일반적으로 각 선택이 다음 단계의 선택에 영향을 미치지 않거나 최소한의 영향을 미치는 상황에서 매 순간 최적의 선택을 하는 것입니다. 그러나 이 문제에서는 모든 그룹을 미리 분석하고, 피로도 합계가 높은 순서로 처리하므로, Greedy 알고리즘에서 요구하는 순간적인 최적의 선택이 이루어지지 않습니다.
나의 코드를 업그레이드
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class 광물캐기_정답 {
public static void main(String[] args) {
Solution solution = new Solution();
int[] arr = {1, 3, 2};
String[] arr2 = {"diamond", "diamond", "diamond", "iron", "iron", "diamond", "iron", "stone"};
int result = solution.solution(arr, arr2);
System.out.println(result);//12
}
static class Solution {
public int solution(int[] picks, String[] minerals) {
int len = Math.min(minerals.length, (picks[0] + picks[1] + picks[2]) * 5);
List<Part> mineralsList = new ArrayList<>();
for (int i = 0; i < len; i += 5) {
int diamondCount = 0;
int ironCount = 0;
int stoneCount = 0;
for (int j = 0; j < 5 && i + j < minerals.length; j++) {
switch (minerals[i + j]) {
case "diamond":
diamondCount++;
break;
case "iron":
ironCount++;
break;
case "stone":
stoneCount++;
break;
}
}
mineralsList.add(new Part(diamondCount, ironCount, stoneCount));
}
// 피로도 합계가 높은 순서대로 정렬
Collections.sort(mineralsList, (p1, p2) -> p2.calculateFatigue() - p1.calculateFatigue());
int result = 0;
int index = 0;
// 다이아몬드 곡괭이 사용
for (int i = 0; i < picks[0] && index < mineralsList.size(); i++, index++) {
result += mineralsList.get(index).getFatigue(0);
}
// 철 곡괭이 사용
for (int i = 0; i < picks[1] && index < mineralsList.size(); i++, index++) {
result += mineralsList.get(index).getFatigue(1);
}
// 돌 곡괭이 사용
for (int i = 0; i < picks[2] && index < mineralsList.size(); i++, index++) {
result += mineralsList.get(index).getFatigue(2);
}
return result;
}
class Part {
private int diamondCount;
private int ironCount;
private int stoneCount;
public Part(int diamondCount, int ironCount, int stoneCount) {
this.diamondCount = diamondCount;
this.ironCount = ironCount;
this.stoneCount = stoneCount;
}
// 피로도 계산 메서드
public int calculateFatigue() {
return diamondCount * 25 + ironCount * 5 + stoneCount * 1;
}
// 특정 곡괭이로 광물을 캘 때의 피로도 반환 메서드
public int getFatigue(int pickType) {
switch (pickType) {
case 0: // 다이아몬드 곡괭이
return diamondCount * 1 + ironCount * 1 + stoneCount * 1;
case 1: // 철 곡괭이
return diamondCount * 5 + ironCount * 1 + stoneCount * 1;
case 2: // 돌 곡괭이
return diamondCount * 25 + ironCount * 5 + stoneCount * 1;
default:
return 0;
}
}
}
}// Solution class end
}//class end
다른 방법으로 풀기
BFS (너비 우선 탐색) 또는 DFS (깊이 우선 탐색): 비효율적
- 이 문제는 상태 공간 탐색, 최적의 해를 구하는 방식이 아니다.
- BFS와 DFS는 그래프나 트리 구조를 탐색
- 최단 경로를 찾기, 모든 가능한 해를 탐색
주어진 문제는 탐색이 아닌, 정렬과 선택의 문제
Greedy: 적합
- 탐욕 알고리즘은 현재 상황에서 가장 최선의 선택을 반복적으로 하여 최적의 해를 구하는 방식
- 각 그룹의 피로도 합계를 기준으로 정렬
- 가장 적은 피로도를 소모하는 곡괭이를 선택
- 최대한 효율적으로 광물을 캐는 것이 목표
- Greedy 알고리즘은 매 순간 최선의 선택을 하도록 설계
Greedy 알고리즘 접근 방식
현재까지의 선택이 앞으로의 선택에 미치는 영향을 최소화하면서, 각 단계에서 가능한 최선의 선택을 하는 식으로 문제를 풀어야 합니다.
- 그룹마다 실시간 선택: 각 그룹을 다룰 때마다, 그 그룹에 대해 현재 가장 적합한 곡괭이를 선택합니다. 이 선택은 이전에 사용한 곡괭이의 수량과 해당 그룹의 광물 구성에 따라 결정됩니다.
- 실시간으로 업데이트: 매 순간, 남아있는 곡괭이의 상태를 실시간으로 업데이트하고, 다음 선택을 그에 맞추어 조정합니다.
즉, 진정한 Greedy 접근법에서는 문제를 한꺼번에 처리하는 대신, 가능한 한 적은 정보를 바탕으로 매 순간 최적의 선택을 하는 전략을 사용해야 합니다.
import java.util.ArrayList;
import java.util.List;
public class 광물캐기_그리디 {
public static void main(String[] args) {
Solution solution = new Solution();
int[] arr = {1, 3, 2};
String[] arr2 = {"diamond", "diamond", "diamond", "iron", "iron", "diamond", "iron", "stone"};
int result = solution.solution(arr, arr2);
System.out.println(result);//12
}
static class Solution {
public int solution(int[] picks, String[] minerals) {
int len = Math.min(minerals.length, (picks[0] + picks[1] + picks[2]) * 5);
List<Mineral> mineralsList = new ArrayList<>();
for (int i = 0; i < len; i += 5) {
int diamondCount = 0;
int ironCount = 0;
int stoneCount = 0;
for (int j = 0; j < 5 && i + j < minerals.length; j++) {
switch (minerals[i + j]) {
case "diamond":
diamondCount++;
break;
case "iron":
ironCount++;
break;
case "stone":
stoneCount++;
break;
}
}
mineralsList.add(new Mineral(diamondCount, ironCount, stoneCount));
}
int result = 0;
for (Mineral mineral : mineralsList) {
int pickToUse = -1;
int minFatigue = Integer.MAX_VALUE;
// 곡괭이를 선택, 각각의 곡괭이로 광물을 캔 피로도 구함 -> 그중에서 최소 피로도를 선택
for (int i = 0; i < 3; i++) {
if (picks[i] > 0) {
int fatigue = mineral.getFatigue(i);
// 최소의 값을 구하는 방법
if (fatigue < minFatigue) {
minFatigue = fatigue;
pickToUse = i;
}
}
}
// 선택된 곡괭이를 사용하여 피로도 추가하고 곡괭이 수량 감소
if (pickToUse != -1) {
result += minFatigue;
picks[pickToUse]--;
}
}
return result;
}
class Mineral {
private int diamondCount;
private int ironCount;
private int stoneCount;
public Mineral(int diamondCount, int ironCount, int stoneCount) {
this.diamondCount = diamondCount;
this.ironCount = ironCount;
this.stoneCount = stoneCount;
}
// 특정 곡괭이로 광물을 캘 때의 피로도 반환 메서드
public int getFatigue(int pickType) {
switch (pickType) {
case 0: // 다이아몬드 곡괭이
return diamondCount * 1 + ironCount * 1 + stoneCount * 1;
case 1: // 철 곡괭이
return diamondCount * 5 + ironCount * 1 + stoneCount * 1;
case 2: // 돌 곡괭이
return diamondCount * 25 + ironCount * 5 + stoneCount * 1;
default:
return 0;
}
}
}
}// Solution class end
}//class end
