광물 캐기(8번 케이스 해결)

문제: https://school.programmers.co.kr/learn/courses/30/lessons/172927

문제설명

• 주어진 파라미터: 곡괭이 수 int[] picks, 광물 순서 String[] minerals
  • picks → [dia, iron, stone]
  • mineral → 광물 이름 diamond, iron, stone
• 반환값: 작업을 끝낼때까지 필요한 최소한의 피로도 int
• 마인이 다이아, 철, 돌 각각 0-5개 → 각 곡괭이는 광물 5개 캔 후에는 더이상 사용 불가
• 광물 캘때는 피로도 소모
• 규칙
  • 곡괭이 1개 사용
  • 한번 사용한 곡괭이는 사용할 수 없을때까지 사용
  • 광물 순서대로 캐기
  • 광산 끝나거나 곡괭이 끝날때까지

풀이방식

1. (방식1) 우선순위 큐로 다이아 → 철 → 돌 순서로 정렬을 해서 하나씩 꺼내면서 처리
   1. 5개 기준으로 생각(5개씩 캐기때문)
   2. 5개씩 돌면서 가장 많은 광물을 하나씩 리스트에 추가
   3. 해당 리스트를 사용해 광물을 다시 돌면서 계산
2. 광물 길이가 최대 50이라 수행시간에 문제가 되지는 않음

코드

import java.util.*;

class Solution {
    public int solution(int[] picks, String[] minerals) {
        int answer = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
          if(a[0] != b[0]){
              return b[0] - a[0];
          }else if(a[1] != b[1]){
              return b[1] - a[1];
          }else{
              return a[2] - b[2];
          }
        });

        int diamond = picks[0];
        int iron = picks[1];
        int stone = picks[2];

        int[] list = new int[3];

        // pq에 5개 단위로 넣기
        for(int i = 0; i < minerals.length; i++){
            String mineral = minerals[i];

            if(mineral.equals("diamond")){
                list[0]++;
            }else if(mineral.equals("iron")){
                list[1]++;
            }else{
                list[2]++;
            }

            if(i % 5 == 4 || i == minerals.length -1 ){
                pq.offer(list);
                list = new int[3];
            }
        }

        // pq에서 하나씩 뽑으면서 계산
        while(!pq.isEmpty()){
            if(diamond == 0 && iron == 0 && stone == 0){
                break;
            }

            int[] cur = pq.poll();
            int curD = cur[0];
            int curI = cur[1];
            int curS = cur[2];

            if(diamond != 0){
                answer += curD + curI + curS;
                diamond--;
            }else if(iron != 0){
                answer += (curD*5) + curI + curS;
                iron--;
            }else{
                answer += (curD*25) + (curI*5) + curS;
                stone--;
            }

        }

        return answer;
    }
}

⇒ 8번 테스트케이스 실패 → 광물을 순서대로 캐야한다는 규칙 위반

picks: [1,1,0]
minerals: [stone, stone, stone, stone, stone, iron, iron, iron, iron, iron, diamond]
일 경우, pq에는 diamond, iron, stone으로 들어가고 결국 stone은 캐지않는 반례가 발생하게 된다.

→ 곡괭이 수가 부족하다면 곡괭이 수에 해당하는 그룹만큼 광물을 줄여버리기

import java.util.*;

class Solution {
    public int solution(int[] picks, String[] minerals) {
        int answer = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
          if(a[0] != b[0]){
              return b[0] - a[0];
          }else if(a[1] != b[1]){
              return b[1] - a[1];
          }else{
              return a[2] - b[2];
          }
        });

        int diamond = picks[0];
        int iron = picks[1];
        int stone = picks[2];
        int toolsSum = diamond + iron + stone;
        int toolsCnt = 0;

        int[] list = new int[3];

        // pq에 5개 단위로 넣기
        for(int i = 0; i < minerals.length; i++){
            String mineral = minerals[i];
            

            if(mineral.equals("diamond")){
                list[0]++;
            }else if(mineral.equals("iron")){
                list[1]++;
            }else{
                list[2]++;
            }

            if(i % 5 == 4 || i == minerals.length -1 ){
                if(toolsCnt == toolsSum) break;
                toolsCnt++;
                
                pq.offer(list);
                list = new int[3];
            }
        }

        // pq에서 하나씩 뽑으면서 계산
        while(!pq.isEmpty()){
            if(diamond == 0 && iron == 0 && stone == 0){
                break;
            }

            int[] cur = pq.poll();
            int curD = cur[0];
            int curI = cur[1];
            int curS = cur[2];

            if(diamond != 0){
                answer += curD + curI + curS;
                diamond--;
            }else if(iron != 0){
                answer += (curD*5) + curI + curS;
                iron--;
            }else{
                answer += (curD*25) + (curI*5) + curS;
                stone--;
            }

        }

        return answer;
    }
}

곡괭이 수만큼 그룹을 줄이는 코드

if(i % 5 == 4 || i == minerals.length -1 ){
    if(toolsCnt == toolsSum) break;
    toolsCnt++;
    
    pq.offer(list);
    list = new int[3];
}

---

참 어렵쥬잉~?