Intro. 이 문제의 난이도.
이 문제가 처음 나왔을 때 도전했다가 못 해냈다.
비교적 나온지 2주 정도 지난 문제로
2023년 4월 11일 기준으로 대략 938명
거의 1,000명에 가까운 사람들이 문제를 풀었다.
계속 풀면서 생각을 거듭하고, 여러 답안 코드들도 봤지만,
나와 맞지 않았다.
설명 되어 있는 부분들이 있지만,
ChatGPT마냥 번호 메김 설명이나 주석 설명은
사실 개인적으로 공부할 때 별 도움이 되지 않았다.
정말 저 부분이 어떤 아이디어인지 세세하게 가져가고 싶은 부분에 대한
공유와 접근 방식이 잘 없는 게 아쉬운 것 같다.
그래서 오늘은 2주 가까이 문제를 접하고 보면서 겪었던 이야기와
놓쳤고, 그래서 그 놓쳤던 부분을 어떻게 잡았는지 등의
여러가지 내용이 들어가 역시 길 예정이다.
이번 코드는 이전 코드들과는 다르게 길다.
그리고
개인적으로 import 관련해서 * 찍고 전체를 활용하는 거 자체도
선호하지 않는다. 가령, StringBuilder 와 같은 객체를 선언하는데도
해당 import를 쓰는 경우도 있는 걸 봤기 때문인데,
학습 할 때는 의도적으로 최대한 import를 쓰려고 한다.
다만, 앞서 말한 것처럼 학습 이외의 별로 크게 상관 없을 거 같고,
명시적으로 보지 않아도 되는 편의에 치우친 경우에는 사용할 수도 있다.
다시, 이 문제의 난이도에 대해서 잠시 이야기 해 보면,
핵심 아이디어!
위의 핵심 아이디어 자체는 떠올리는데 크게
오랜 시간이 걸리지 않는다. 다만 구현의 경우가,
이 문제를 어렵게 만들었다.
특히 정렬의 기준이 여러가지로 보이는 문제의 경우,
위의 문제의 경우, 곡괭이의 개수부터, 광물의 개수,
광물에 대한 피로도 등등 따져야 할 부분이 여러가지가 된다면
이러한 요소 요소들에서 무엇을 어떻게 연관지어서 정렬하고
정답으로 만들어 낼 것인가?
이것이 굉장히 고민되는 요소가 아닐 수 없다.
즉, 핵심 아이디어의 핵심에 해당하는 정렬의 구현을
얼마나 잘 해내느냐가 관건이다.
질문하기를 보면 DFS를 활용한 구현이라던지,
BFS의 개념을 활용한다던지 등의 내용이 많다.
그리디하게 풀었어요! 이런 글들도 많은데,
솔직히 이 문제는 그리디라고 보기 조금 민망한 느낌이다.
가장 앞에서 뽑는 경우가 가장 베스트가 되게
모두 정렬해 둔 다음에 가장 적합하게 제거해 나간다.
그리디 치고는 너무 정교하고 깔끔하고 무조건적으로
최적해에 도달할 수 있기 때문이다.
그래서 개인적으로는 해당 문제를 정렬 그리고 구현 이렇게 묶고 싶다.
그리디라면 배열의 길이가 다르다던지 100원 500원 뭐 이런 여러가지 값들이
더 나오면서 조건 분기가 더 깔끔하지 않았을까 싶기 때문
(근데 그리디도 정렬해서 깔끔하게 푸는 수강시간 막 그런 문제들도 있어서
그리디라고 할 수도 있는데 솔직히 위의 문제 자체도 그리디라고 하면 그리디인데
정렬이 어렵지 저 문제도 그리디의 개념으로 접근한다는 건 어려운게 아니기에
정렬과 구현에 집중해서 서술하겠다.)
애초에 나 역시 코딩을 짱 잘하는 베스트 지니어스가 아니기 때문에...
이상한 소리나 틀린 게 있으면 쓴소리와 다독임을 부탁드립니다.
참고로 제일 짧은 정답 코드는 스트림을 활용해 15줄로 구현되어 있다.
개인적으로 풀고 해당 코드들도 확인해 보면서 스트림 학습을 해보는 것도 좋을 것 같다 :)
오늘 준비한 코드부터 보시죠.
import java.util.Queue;
import java.util.LinkedList;
import java.util.Map;
import java.util.HashMap;
import java.util.TreeMap;
import java.util.Comparator;
class Solution {
public int solution(int[] picks, String[] minerals) {
int sum = picks[0] + picks[1] + picks[2];
final int MAX_PICK = Math.min(sum,(minerals.length+4)/5);
int[] newPicks = new int[3];
Map<Integer, Queue<Character>> map = new HashMap<>();
int temp = MAX_PICK;
int pickIdx = 0;
while(temp > 0){
while(picks[pickIdx]==0)pickIdx++;
picks[pickIdx]--;
newPicks[pickIdx]++;
temp--;
}
int mineralIdx = 0;
while(temp < MAX_PICK){
Queue<Character> queue = new LinkedList<>();
while(mineralIdx < minerals.length && queue.size() < 5)
queue.add(minerals[mineralIdx++].charAt(0));
map.put(temp++, queue);
}
return min(newPicks, map, temp);
}
private int min(int[] picks, Map<Integer,Queue<Character>> slice, int max){
int answer = 0;
Map<Integer, LinkedList<Integer>> map = new TreeMap<>(Comparator.reverseOrder()); //가장 큰 값, slice에 접근할 수 있는 i를 value로 가지는 트리맵 내림차순//값이 겹칠 수도 있음...!
for(int i : slice.keySet()){
int sum = 0;
Queue<Character> queue = slice.get(i);
int size = queue.size();
while(size > 0){
char c = queue.poll();
if(c == 'd') sum+= 25;
else if(c == 'i')sum +=5;
else sum+=1;
queue.offer(c);
size--;
}
if(map.containsKey(sum)) map.get(sum).add(i);
else{
LinkedList<Integer> list = new LinkedList<>();
list.add(i);
map.put(sum,list);
}//키가 되는 피로도 여러개일 가능성
}
int idx = 0;
for(LinkedList<Integer> temp : map.values()){
for(int key : temp){
Queue<Character> queue = slice.get(key);
int size = queue.size();
while(!queue.isEmpty()){
while(picks[idx] == 0)idx++;
char c = queue.poll();
if(idx == 0) answer+=1;
else if(idx==1) {
if(c=='d') answer+=5;
else answer += 1;
}else{
if(c=='d') answer+=25;
else if(c=='i') answer += 5;
else answer += 1;
}
}
picks[idx]--;
}
}
return answer;
}
}import 를 모두 포함해서 대략 75줄!
이전까지의 최대한 짧게 쓰려던 노력들이 무색하게 길다.
해당 문제의 구현을 손으로 끄적이며 크게 4개로 나누었었는데
그 전에
핵심 아이디어를 다시 짚고 넘어가자.
<문제 내용의 규칙 부분을 발췌했다.>
마인은 다음과 같은 규칙을 지키면서 최소한의 피로도로 광물을 캐려고 합니다.
- 사용할 수 있는 곡괭이중 아무거나 하나를 선택해 광물을 캡니다.
- 한 번 사용하기 시작한 곡괭이는 사용할 수 없을 때까지 사용합니다.
- 광물은 주어진 순서대로만 캘 수 있습니다.
- 광산에 있는 모든 광물을 캐거나, 더 사용할 곡괭이가 없을 때까지 광물을 캡니다.
솔직히 첫 번째 조건은 과친절이다. 뭐 아니면 마인이는 광전사여서 두 손으로 캐는 버스터 모드를 쓸 수 있다. 와 같은 조건을 추가할 수 있을지도 모르니 표시해줬다.
개인적으로는 두 번째 조건부터 3, 4번 조건이 해당 문제에서 주효하게 작용한다.
2번째의 강조 표시한 사용할 수 없을 때까지는
4번째 조건과 결합되어, 광산에 있는 모든 광물을 캐거나, 또는 5번의 광물을 모두 캘 때
라는 형태가 된다.
그리고 3번째 조건을 보면 광물은 순서대로 캘 수 있다.
즉, 임의로 가장 적절한 구간을 찾는 게 아니라, 첫 번째 부터 자르는 걸 규칙으로 한다.
그리고 다시 4번째를 마지막으로 보면,
광산에 있는 모든 광물을 캤거나, 더 사용할 곡괭이가 없는 경우까지 광물을 캔다.
위의 4번째에 조금 꽂혀서 MAX_PICK가 같은 변수를 만들었다.
처음에는 전역변수로 클래스 내에 final 상수로 만들려고 했는데,
그러면 메서드가 호출될 때 마다 값이 변경되기 때문에, final에 맞지 않아서
메서드 내에 변수를 선언했다. 해당 값이 유의미하진 않지만,
머릿 속에 인식시켜 두기 위한 장치로 만들었다.
기본적으로 총 4가지의 과정을 거쳐서 답을 도출한다.
이하는 해당 내용에 대한 상술과 해당 코드를 가지고 와서 상세 설명을 한다.
- 4번 규칙을 위한 새로운 곡괭이 배열 생성.
- 값 정렬을 위한 formating.
- 값 정렬하기.**
- 정렬한 값을 바탕으로 정답 도출.
개인적으로 3번째 부분 값 정렬의 부분에서 아이디어를 여럿 쓰고,
고민을 많이했다. 내림차순 정렬이라던가
(안 해도 문제는 아니지만, 그래도 기본적으로 정렬하는 연습 차원..)
위의 4가지 과정을 고민하면서 자연스럽게 메서드가
추가 되었는데
처음에 공부할 때든, 나 역시 지금도
메서드나 클래스를 새로 생성하는 게 번거롭고
어렵고 힘들고 무섭고, 어떤 기준으로
만들어야 하나...고민을 많이 한다.
뭐 결과적으로 대체러 그렇겠지만, 메서드를 나눈 이유는
간단하다. 의미를 분할하기 위해서인데,
첫 번째 메서드 solution에서는 1~2의 과정만 만들었다.
3~4의 과정은 이하의 min 이라는 메서드에서 구현했다.
이렇게 하면 문제를 2개 푸는 느낌이긴 하지만,
한 편으로는 한 문제를 쪼개서 푸는 형태가 되기 때문에,
하나의 메서드를 굉장히 작게 디자인 할 수 있다는 이점이 있다.
더 작게 만들 수도 있는 것이다.
그래서 나 같은 경우에는 각각 30줄 정도의 코드로
의미를 분할했다고 볼 수 있다.
실제로 min 메서드를 만들고 작성해 나갈 때는
더 이상 위의 1~2 과정을 고려하지 않아도 되기 때문에
개인적으로 조금씩 연습해 보는게 어떨까 싶다.
이제 각각의 의미 단위의 구현을 알아 보자.
1. 4번 규칙을 위한 새로운 곡괭이 배열 생성.
int sum = picks[0] + picks[1] + picks[2];
final int MAX_PICK = Math.min(sum,(minerals.length+4)/5);
int[] newPicks = new int[3];
Map<Integer, Queue<Character>> map = new HashMap<>();
int temp = MAX_PICK;
int pickIdx = 0;
while(temp > 0){
while(picks[pickIdx]==0)pickIdx++;
picks[pickIdx]--;
newPicks[pickIdx]++;
temp--;
}다른 분들의 코드를 보면 그리디하게 풀었다고 하시는 부분의
위의 요소를 활용한 것과 같다.
이차원 배열로 만드신 분들도 있고 다양한데,
나 같은 경우에는 맵을 선택했다.
맵을 선택한 이유는 맵의 탐색 방식 자체가 O(1)이기 때문.
다만, 공간 복잡도가 올라가는 게 맵의 큰 단점이다.
맵의 시간 복잡도는 1이지만, 공간 복잡도
즉, 메모리 사용이 크기 때문에 순수하게 좋은 방식이다!
라고 단정할 수는 없다.
탐색 방식이 O(1)이라는 말의 의미는
아는 분도 계시겠지만 모르는 분들을 위해서
짚고 넘어가자면,
배열의 경우도 탐색이 O(1)로 이루어지지만
공간이 고정된다는 단점이 있고, 값의 추가 삭제가
리스트에 비해 느리다는 특징이 있다.
반면 리스트는 값의 추가, 삭제에 있어서 기능이
배열에 비해 훨씬 빠르며 공간도 연속된 공간을
차지하는게 아니기 때문에 메모리 사용이 훨씬 자유롭다.
다만 배열과 다르게 탐색의 경우, 자신이 찾는 값의 인덱스 만큼
무조건 시간이 소요되기 때문에 이점이 적다.
그래서 나는 개인적으로 배열과 리스트의 두 가지 특징이 절충된
탐색이 O(1)이지만,(키 값을 알면 바로 value값에 접근하는!)
리스트처럼 배열과 다르게 고정되지 않고 값을 추가할 수 있는
특징을 가진 맵을 활용했다.
위의 장점으로만 고려해서 맵을 가져왔다고는 하지만,
맵 자체가 엄청 빠르거나 하진 않다.
앞서 말한 Map의 단점이 이를 상쇄하는 것도 있고,
내가 이 문제 자체를 복잡하게 키와 밸류의 형태를
다양하게 가지는 형태로 잡았기 때문.
하지만, 그래도 위와 같은 이유로 Map을 골랐고,
HashMap의 경우는 값의 정렬을 보장하지 않기 때문에
값의 정렬이 보장되는 TreeMap을 통해 값을 정렬해 줄 예정.
이제 formating 부분을 다시 살펴 보면,
4번조건 상 가능한 곡괭이의 최대 개수는 둘 중 하나가 된다.
채굴 가능한 광물 수의 한계치 또는 곡괭이 수 중 적은 쪽.
채굴은 5개 단위로 되는데
이때 Math.ceil같은 메서드를 통해 올림을
할 수도 있지만
나의 올림의 형태를 보면 (나눌 값 + 4(나누는 값-1))/5(나누는값)
형태를 취했다. 일종의 최적화인데 위와 같은 형태로 하면
메서드 사용없이 올림이 가능하다 :)
자주 쓰는 방식 중 하나여서 한 번 부연했다.
나머지는 MAX_PICK 형태처럼 Math.min()으로 해서 값을 담아줬다.
새로운 곡괭이 배열을 만들 준비가 되었다.
해당 값을 가지고, 기존의 값의 큰 값에서 빠져나가게 해
새로운 곡괭이 배열을 만든다.
각 인덱스의 값이 0이라면, idx가 바뀌게 while을 만들었다.
이제 그 위에 선언된 Map을 잠시 살펴 보자.
Value를 Queue로 한 이유가 크진 않다.
List로 해서 remove/add를 해도 같고
실제로 그렇게도 했는데 중간에 PriorityQueue를
활용하면 어떨까 싶어서 만들다가 pq로 하면 더하는 값이
무조건 큰 값만 앞으로 오는 문제가 생겨서 기각하면서 Queue가
됐다. List로 해도 됐지만,
저 문제 코딩할 때 모바일 밖에 없는 환경에서 한 거라
부디 해당 부분은 양해를 부탁 드립니다 :)
Queue queue를 밸류로 해서 String[] 을
character로 나눠줘서 연산 비교 및 단위값
(diamond -> d로 형태를 간소화했다.)
웹 개발이나 더 다양한 형태였다면 언어가
전체 의미를 사용하는게 이점이겠지만 문제기 때문에 줄였다.
이제 2번째 작업 formating을 해 보자.
2. 값 정렬을 위한 formating.
int mineralIdx = 0;
while(temp < MAX_PICK){
Queue<Character> queue = new LinkedList<>();
while(mineralIdx < minerals.length && queue.size() < 5)
queue.add(minerals[mineralIdx++].charAt(0));
map.put(temp++, queue);
} 해당 코드 역시 규칙을 생각하면서 나아가면 된다.
의미단위로 끊는 queue의 크기는 5일 넘어서는 안 되며,
또한 배열의 크기를 넘어서도 안 된다.
위에서 한 번 사용된 temp라는 int를 재탕해
구현했다. MAX_PICK을 상수로 두면서 따로 해당 부분을
크게 신경쓰지 않고 작성해 나갔다. :)
3. 값 정렬하기.
이제 formating을 마쳤다.
이후에 메서드를 만들었는데, 보면 매개변수가 3개다.
private int min(int[] picks, Map<Integer,Queue> slice, int max){int answer = 0; return answer;} 정답도 해당 메서드에서 구현할 것이기 때문에
로 두면
전혀 다른 새로운 문제로 리프레시 하는 기분이다!
물론 매개변수를 slice처럼 줄리는 거의 없겠지만...
int max라는 한계치를 줘서 PICK_MAX도 사용할 수 있게 넘겨줬다.
Map<Integer, LinkedList<Integer>> map = new TreeMap<>(Comparator.reverseOrder()); //가장 큰 값, slice에 접근할 수 있는 i를 value로 가지는 트리맵 내림차순//값이 겹칠 수도 있음...!
for(int i : slice.keySet()){
int sum = 0;
Queue<Character> queue = slice.get(i);
int size = queue.size();
while(size > 0){
char c = queue.poll();
if(c == 'd') sum+= 25;
else if(c == 'i')sum +=5;
else sum+=1;
queue.offer(c);
size--;
}
if(map.containsKey(sum)) map.get(sum).add(i);
else{
LinkedList<Integer> list = new LinkedList<>();
list.add(i);
map.put(sum,list);
}//키가 되는 피로도 여러개일 가능성
} 정렬을 하는 코드 부분.
솔직히 Comparator 가 아직 헷갈린다.
Collections도 있고, stream에는 Collector 도 있다.
Comparators 이렇게 쓸 때도 많다.
그래서 헷갈리는 만큼 자주 쓰면서 익숙하게 익히고자
하기 위함이니 저런 것도 있구나! 하고 넘어가 주시거나
외우는 꿀팁 있으면 알려죽시면 감사하겠습니다.
그리고 메서드를 쓴 이유가 하나 더 있는데 TreeMap을 만들 때
해당 맵의 이름을 편하게 map으로 단순하게 작성할 수 있기 때문이다.
하나의 메서드 안에서는 계속 다른 변수로 만들어 줘야 하지만
의미 단위에서 같은 별개의 영역이라 편하게 사용했다.
정렬을 할때는 stone의 피로도 fatigue를 기준으로 작성했으며,
이때 !queue.isEmpty()로 손쉽게 구현해주면 좋겠지만
자바의 경우 해당 queue가 얇게 복제 되기 때문에,
즉 똑같은 참조값을 쓰기 때문에
그렇게 소모해 버리면 이후 답을 도출하고자 할 땐
아무것도 남지 않기 때문에
별도의 int size 를 만들고 해당 size로 횟수를 결정하고
queue를 넣었다 뺐다의 형태로 만들었다.
그리고 여기서 만든 피로도의 최대치의 경우!!
겹칠 수 있다!
맵의 경우, 키가 같다면 밸류의 경우 덮어 씌워지기 때문에
해당 값의 경우 LinkedList를 활용해 관리했다.
위에서 말했지만 이 경우는 Queue를 쓰나 List를 활용하나
큰 차이가 없다. 애초에 Queue자체도 LinkedList로 구현 되었기 때문에
크게 보면 한 식구(?)
뭐 어쨋든 개인적으로는 피로도가 겹칠 수 있기 때문에 인덱스를
2개 이상 가질 수 있다는 부분의 아이디어를 Miss 내고 오래 헤맸기에
해당 부분이 크게 주요하다고 생각했다.
마지막. 정렬한 값을 바탕으로 정답 도출.
대망의 마지막 코드
뭐 위의 과정을 봤으면 크게 별건 없다. 다만
개인적으로는 TreeMap을 쓸 때는 .values()를 자주 쓴다.
어차피 키를 통해 value에 접근하고 싶을 때 자주 사용하는 방식이
개인적으로 TreeMap이기 때문에
키를 가져오고 그 키로 value를 불러오는 과정들이 생략되는 점도 좋다.
다만 이번 values()의 경우 LinkedList<>로 구현되었기에
for를 두 번 써줬다.
int idx = 0;
for(LinkedList<Integer> temp : map.values()){
for(int key : temp){
Queue<Character> queue = slice.get(key);
int size = queue.size();
while(!queue.isEmpty()){
while(picks[idx] == 0)idx++;
char c = queue.poll();
if(idx == 0) answer+=1;
else if(idx==1) {
if(c=='d') answer+=5;
else answer += 1;
}else{
if(c=='d') answer+=25;
else if(c=='i') answer += 5;
else answer += 1;
}
}
picks[idx]--;
}
}
return answer;
} 위의 과정이 답을 구하기 위한 과정으로
처음 새로운 배열을 만들 때와
세 번째 정렬을 할 때의 과정이 모두 녹아 들었다.
idx = 0이면 다이아 곡괭이 1이면 쇠, 2면 돌 곡괭이며
각각 피로도가 1,1,1/5,1,1/25,5,1이 된다.
3번째에서는 size를 두고 관리했지만
이번에는 바로 삭제해줘도 무관하기 때문에 해당 형태로 구현해줬다.
이렇게 if else 를 각각의 분기에 맞춰서 작성하면 끝이난다.
코드가 길어 보이지만 이처럼 의미 단위로 나눠서 생각해 보고,
메서드 단위로 나눠서 생각하는 과정이
익숙하고 순식간에 이루어진다면 해당 문제도 분명
20~30분 정도면 구현할 수 있지 않을까 싶다.
물론 그런 과정이 어렵고 힘들기 때문에 계속 연습하고
도전하고 시도하는 거지만, 언젠가는 되지 않을까?
