일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
Tags
- ac 5430번
- 프로그래머스
- replace()
- 백준 2467번 용액 자바 - 이분탐색
- 코틀린기초
- StringBuilder
- dp
- map
- 18111번 마인크래프트 - java 구현
- 백준 14938번 서강그라운드
- kotlin
- append
- toUpperCase
- hash
- 프로그래머스 java
- HashSet
- 백준 3190번
- 백준 2473번 세 용액 - java
- 최소 힙 1927
- Stack
- mysql hy000 에러
- 백준 1541
- StringTokenizer
- 백준 1197번 최소 스패닝 트리 - java
- HashMap
- 프로그래머스 자바
- 백준 1806번 부분합 java
- 백준 1647번 도시 분할 계획 - java
- 백준 1043번 거짓말 - java 분리 집합
- Java
Archives
- Today
- Total
말하는 컴공감자의 텃밭
프로그래머스 lv2 광물캐기- greedy 본문
728x90
문제를 읽어보면
곡괭이의 종류에 따라 광물을 캐는 효율이 다르다.
1개의 곡괭이를 들면 5개의 광물을 캐게 된다.
모든 광물을 캐거나 곡괭이가 없을때까지 진행 후, 가장 효율적으로 캐는 방법을 구하는 문제다
바로 그리디가 떠올랐고, 한번 곡괭이를 쓸때 5개의 광물을 캐기 때문에
5개의 광물씩 묶어 그룹화 하고 정렬을 통해 가장 피로도가 높은 집단에서부터 가장 좋은 곡괭이를 소모시키게 작성했다.
그룹에는 총 광물의 가치가 몇인지, 다이아, 철, 돌의 개수 를 포함시켰다.
groups.sort(Comparator.comparingInt(Group::getValue).reversed());
다만 예외사항이 존재했다.
만약 광물이 6개고 ["stone", "stone", "stone", "stone", "stone", "diamond"] 로 주어졌다고 가정하자.
곡괭이는 [0,0,1] 로 주어진 경우 무조건 피로도가 높은 순서로 정렬하기 때문에 diamond를 캐게된다.
그냥 돌만캐면 5였지만 다이아를 캐게되므로 25가 되게 된다.
따라서
if (minerals.length > maxMinerals) {
minerals = java.util.Arrays.copyOf(minerals, maxMinerals);
}
을 통해 정렬하기 전, 곡괭이가 캘수있는 만큼의 광물 개수로만 지정해주고 정렬하면 된다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 | import java.io.*; import java.util.*; class Solution { public int solution(int[] picks, String[] minerals) { int answer = 0; int totalPicks = picks[0] + picks[1] + picks[2]; int maxMinerals = totalPicks * 5; // 광물을 최대 채굴 가능 수로 제한 if (minerals.length > maxMinerals) { minerals = java.util.Arrays.copyOf(minerals, maxMinerals); } List<Group> groups = checkValue(minerals); groups.sort(Comparator.comparingInt(Group::getValue).reversed()); for (Group group : groups) { if (picks[0] > 0) { answer += group.getDiamondCount() + group.getIronCount() + group.getStoneCount(); picks[0]--; } else if (picks[1] > 0) { answer += group.getDiamondCount() * 5 + group.getIronCount() + group.getStoneCount(); picks[1]--; } else if (picks[2] > 0) { answer += group.getDiamondCount() * 25 + group.getIronCount() * 5 + group.getStoneCount(); picks[2]--; } else { break; // 모든 곡괭이를 다 사용한 경우 종료 } } return answer; } public List<Group> checkValue(String[] minerals) { int mineralsGroups = (minerals.length + 4) / 5; // 5개씩 나눌 그룹 수 계산 List<Group> groupsValue = new ArrayList<>(); for (int i = 0; i < minerals.length; i += 5) { int groupValue = 0; int diamondCount = 0; int ironCount = 0; int stoneCount = 0; for (int j = 0; j < 5 && i + j < minerals.length; j++) { String type = minerals[i + j]; switch (type) { case "diamond" -> { groupValue += 25; diamondCount++; } case "iron" -> { groupValue += 5; ironCount++; } case "stone" -> { groupValue += 1; stoneCount++; } } } groupsValue.add(new Group(groupValue, diamondCount, ironCount, stoneCount)); } return groupsValue; } class Group { private final int value; private final int diamondCount; private final int ironCount; private final int stoneCount; public Group(int value, int diamondCount, int ironCount, int stoneCount) { this.value = value; this.diamondCount = diamondCount; this.ironCount = ironCount; this.stoneCount = stoneCount; } public int getValue() { return value; } public int getDiamondCount() { return diamondCount; } public int getIronCount() { return ironCount; } public int getStoneCount() { return stoneCount; } } } | cs |
728x90
'알고리즘 > Programmers - Java' 카테고리의 다른 글
알고리즘 재활 6일차 - 프로그래머스 괄호 회전하기, 할인 행사 (0) | 2024.08.05 |
---|---|
프로그래머스 lv2 디펜스 게임 - Java 그리디 (1) | 2024.07.29 |
프로그래머스 [PCCE 기출문제] Lv1. 1, 9번 - 자바 (1) | 2023.12.21 |
프로그래머스 PCCE 기출문제 Lv.0 모음 - 자바 (0) | 2023.12.16 |
프로그래머스 - 뒤에 있는 큰 수 찾기 <9점> - 자바 java Stack (0) | 2023.08.04 |
Comments