[코테]프로그래머스 - 광물캐기

문제

설명

제한사항

입출력 예시

문제 요약

• 3가지의 곡괭이를 최소 0개에서 5개까지 보유
• 곡괭이를 통해 3가지 광물을 채굴해야하며, 이 때 광석과 곡괭이의 유형에 따라 피로도가 증가.
• 주어진 곡괭이를 이용하여 광석을 채굴할 때, 가장 낮은 피로도를 사용하는 경우의 피로도를 반환.
• 곡괭이는 순서와 상관없이 선택할 수 있으며 선택 시 5번을 사용해야함.
• 광석을 배열에 주어진 순서대로 채굴해야함.
• 곡괭이를 모두 사용했거나 광석이 없는 경우 채굴을 종료하고 결과를 반환함.

문제 분석

프로그래머스 레벨 2부터는 문제를 단순히 시간복잡도를 판단하여 풀기에는 제한이 있었다. 그래서 최대한 논리의 흐름에 따라 분석을 하려 노력했다. 다음 과정을 거쳐서 문제를 분석했다.

• 곡괭이는 순서가 필요없으니 1개를 선택한 경우 5개의 광물을 캐야하기에 정렬 후 5개로 분리했다.
  (이건 제한사항을 제대로 숙지하지 못해 발생한 오류였다.)
• 곡괭이를 순서대로 순회하며 해당 곡괭이가 있다면 5개씩 그룹화한 광물을 캔다.
• 이 때 피로도를 리스트에 저장하여 가장 낮은 리스트의 값을 정답에 누적한다.
• 누적한 피로도를 광물이 없거나 곡괭이가 모두 소모되면 반환한다.
• minerals의 길이가 최소 5개에서 최대 50개이므로 시간복잡도를 고려 할 필요는 없다고 판단하였음.
• 최소의 피로도를 계산해야하기 때문에 그리디 알고리즘이 적용해야하는 문제라고 생각함.

문제 풀이

실패

슈도코드

public static class 광물 {
	//각각의 광물의 수를 필드로 보유
    
    //getter, setter 보유
}

for(minerals의 길이만큼){
	각각의 광물을 5개씩 잘라서 보유
}

for(picks의 길이만큼){
	if(곡괭이가 없다면){
    	Integer의 최대값을 부여;
    	continue;
    }
    
    //곡괭이가 있다면
   	diamond의 경우 모든 광석을 피로도 1로 계산
    iron의 경우 다이아몬드는 5, 다른 광석은 1로 계산
    stone의 경우 다이아몬드는 25, 철은 5, 돌은 1로 계산
    
    계산된 피로도 리스트에서 최소값을 정답에 누적
    
    사용한 곡괭이는 -1
}

구현코드

package test.level2;

import java.util.*;

public class 광물캐기 {
    /*
     * picks : 곡괭이의 개수, [dia, rion, stone] 순서
     * minerals: 광물들의 순서, 3개의 문자열로 이루어져 있음
     *
     * */

    public static class Mineral {
        private int diamond;
        private int iron;
        private int stone;

        public void setDiamond() {
            this.diamond++;
        }

        public void setIron() {
            this.iron++;
        }

        public void setStone() {
            this.stone++;
        }

        public int getDiamond() {
            return this.diamond;
        }

        public int getIron() {
            return this.iron;
        }

        public int getStone() {
            return this.stone;
        }
    }

    public static int solution(int[] picks, String[] minerals) {
        int answer = 0;

        // 광물을 5개씩 끊어서 리스트에 저장한다.
        List<Mineral> mineralList = new ArrayList<>();
        Mineral mineral = null;
        for (int i = 0; i < minerals.length; i++) {
            if (i == 0) mineral = new Mineral();

            if (minerals[i].equals("diamond")) mineral.setDiamond();
            if (minerals[i].equals("iron")) mineral.setIron();
            if (minerals[i].equals("stone")) mineral.setStone();

            if (mineral.getDiamond() + mineral.getIron() + mineral.getStone() == 5 || i == minerals.length - 1) {
                mineralList.add(mineral);
                mineral = new Mineral();
            }
        }

        // 곡괭이의 종류별로 광물을 순서대로 5개씩 끊어서 피로도를 계산한다.
        for (Mineral target : mineralList) {
            List<Integer> scoreList = new ArrayList<>();
            int temp = 0;

            if (target.getStone() == 5) {
                temp = 5;

                if(picks[2] > 0) {
                    picks[2]--;
                    continue;
                } else if (picks[1] > 0) {
                    picks[1]--;
                    continue;
                }
            }

                for (int i = 0; i < picks.length; i++) {
                    // 해당 곡괭이가 없으면 Max_value를 부여하고 패스한다.
                    if (picks[i] == 0) {
                        scoreList.add(Integer.MAX_VALUE);
                        continue;
                    }

                    if (picks[i] > 0) {
                        if (i == 0) {
                            temp = target.getDiamond() + target.getIron() + target.getStone();
                        }
                        if (i == 1) {
                            temp = (target.getDiamond() * 5) + ((target.getIron() + target.getStone()) * 1);
                        }
                        if (i == 2) {
                            temp = (target.getDiamond() * 25) + (target.getIron() * 5) + (target.getStone() * 1);
                        }
                    }
                    scoreList.add(temp);
                }

            if (picks[0] <= 0 && picks[1] <= 0 && picks[2] <= 0) break;
            // 가장 낮은 피로도를 정답에 더한다.
            int min = Collections.min(scoreList);
            int index = scoreList.indexOf(min);
            picks[index]--;
            answer += min;
        }

        return answer;
    }

    public static void main(String[] args) {
        String[] minerals = {"diamond", "diamond", "diamond", "iron", "iron", "diamond", "iron", "stone"};
        int[] picks = {1, 3, 2};

        System.out.println(solution(picks, minerals));
    }

}

위 상황에서 꼬인 부분은 광석의 순서를 바꾸면 안되는데 바꿔서 계산을 하려고 했던 부분과 곡괭이를 보유한 순서대로 사용하여 피로도가 높은 광석을 채굴하는 것에 대한 비교를 해야하는 부분이 구현되지 못하여 테스트 케이스를 50%만 통과하고 있었다. 이런 부분을 혼자 고민하다가 1시간이 지나서야 다른 사람들의 코드를 참고했다.

나는 문제를 그리디 알고리즘을 사용해야한다고 생각했기에 그리디 알고리즘을 적용한 분의 정답 코드를 참고하였다.

성공

슈도코드

for(mineral의 길이 / 5 + 1만큼){
	광물을 5개 단위로 분리하기 위한 리스트 생성
}

for(List의 길이만큼){
	for(5개 간격으로 5번씩){
    	광물을 리스트에 5개단위로 분리하여 저장
    }
}

if(minerals의 길이가 5의 배수이면){
	마지막 생성되는 리스트는 불필요하므로 삭제
}

if(광물이 곡괭이의 총 수량보다 많다면){
	초과된 광물들 삭제
}

광물들을 다이아, 철, 돌 순으로 정렬하여 피로도가 높은 순으로 리스트를 정렬

각각의 곡괭이로 광물을 순회하며 피로도를 계산하여 누적

구현코드

package test.level2;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import static java.util.Collections.frequency;

public class 광물캐기2 {
    /*
     * picks : 곡괭이의 개수, [dia, rion, stone] 순서
     * minerals: 광물들의 순서, 3개의 문자열로 이루어져 있음
     *
     * */
    public static int solution(int[] picks, String[] minerals) {
        int answer = 0;

        // minerals 5개 단위로 나누기
        List<List<String>> list = new ArrayList<>();
        for (int i = 0; i < minerals.length / 5 + 1; i++) {
            list.add(new ArrayList<>());
        }

        for (int i = 0; i < minerals.length / 5 + 1; i++) {
            // i가 증가할 때마다 5개 단위 요소를 저장
            for (int j = 0 + i * 5; j < 5 + i * 5; j++) {
                if (j >= minerals.length) break;
                list.get(i).add(minerals[j]);
            }
        }

        // 배열의 요소가 5개 단위로 나누어 떨어지면 불필요한 마지막 요소 생성을 방지
        if (minerals.length % 5 == 0) {
            list.remove(list.size() - 1);
        }

        // 곡괭이보다 광물이 많을 경우 해당 광물들 삭제
        int pickSum = picks[0] + picks[1] + picks[2];
        if (pickSum < list.size()) {
            int countWillRemove = list.size() - pickSum;
            for (int i = 0; i < countWillRemove; i++) {
                list.remove(list.size() - 1);
            }
        }

        // 5개 단위로 나눈 Subset을 정렬
        Collections.sort(list, (l1, l2) -> {
            if (frequency(l2, "diamond") == frequency(l1, "diamond")) {
                if (frequency(l2, "iron") == frequency(l1, "iron")) {
                    return frequency(l2, "stone") - frequency(l1, "stone");
                } else {
                    return frequency(l2, "iron") - frequency(l1, "iron");
                }
            } else {
                return frequency(l2, "diamond") - frequency(l1, "diamond");
            }
        });

        // 순서대로 채광
        for(int i = 0; i < picks[0]; i++){
            if (list.isEmpty()) break;
            List<String> currentList = list.get(0);
            for(int j = 0; j < currentList.size(); j++){
                answer += 1;
            }
            list.remove(0);
        }

        for (int i = 0; i < picks[1]; i++){
            if(list.isEmpty()) break;
            List<String> currentList = list.get(0);
            for(int j = 0; j < currentList.size(); j++){
                if(currentList.get(j).equals("diamond"))answer += 5;
                else answer += 1;
            }
            list.remove(0);
        }

        for(int i = 0; i < picks[2]; i++){
            if(list.isEmpty()) break;
            List<String> currentList = list.get(0);
            for(int j = 0; j < currentList.size(); j++){
                if(currentList.get(j).equals("diamond")) answer += 25;
                else if (currentList.get(j).equals("iron")) answer += 5;
                else answer += 1;
            }
            list.remove(0);
        }

        return answer;
    }

    public static void main(String[] args) {
        int[] picks = {1, 3, 2};
        String[] minerals = {"diamond", "diamond", "diamond", "iron", "iron", "diamond", "iron", "stone"};

        System.out.println(solution(picks, minerals));
    }

}

위 코드에서 아쉬운 부분은 각 곡괭이를 사용해서 각자 반복문을 돌리는 코드가 구현된 것이다. 해당 코드를 1개의 반복문 내에서 조건을 변경하여 처리할 수 있을 것 같지만 해당 부분은 나의 개인적인 아쉬움이기에 기능이 구현된 것에 대해서는 내가 놓쳤던 부분들이 다 들어가 있다고 볼 수 있다.

광물을 5개 단위로 리스트에 저장한 것과 불필요한 리스트 및 광물을 사전에 삭제한 것. 마지막으로 5개 단위 광물을 1개의 세트로보고 피로도가 높은 순으로 정렬하여 각각의 곡괭이를 다 소모하면 다음 반복문으로 넘어가는 것까지 내가 놓친 부분이 구현되어 있었다.

아직 알고리즘에 대한 정확한 지식이 없어서 이런 부분들이 제대로 파악되지 못한게 가장 큰 아쉬움인 것 같다는 생각을 했다.

그럼 이만.👊🏽