항해 99 16일차 TIL( 광물캐기 / 프로그래머스)

문제

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

사고과정

문제를 요약하자면 최소한의 피로도로 최대한 광물을 캐는 것이다.

광물 캐는 규칙을 세워보겠다.

돌은 어느 곡갱이로 캐든 피로도가 1로 똑같다. 그러므로 가장 성능이 안 좋은 곡갱이를 우선순위로 사용해야 한다.
돌을 캘 때는 다이아몬드 < 철 < 돌 곡갱이로 우선순위를 돌 것
다이아 몬드를 캘 때는 돌 < 철 < 다이아몬드
철을 캘 때는 돌 < 다이아몬드 < 철
하나의 곡갱이를 선택하면 무조건 연속으로 5개 캐야한다.

1번째 시도

끝나는 상황이 두 개로 나누어진다
- 1. 곡갱이가 부족한 상황
- 2. 곡갱이가 딱 맞거나 충분한 상황

알고리즘 기법으로 생각해보았다.

1. 완전탐색
2. 그리드

완전탐색은 당연히 성공하겠지만 시간초과가 걸릴 것 같아 패스!

그리드는 그 상황에서 최선을 고르는 것이다. 선택 당시 이후에 상황을 고려하지 않는 그리드가 맞는지 긴가 민가 했지만 다른 사람들의 아이디어에서 힌트를 얻었다.

1. 곡갱이가 캘 수 있는 광물의 개수보다 주어진 광물의 개수가 클시 주어진 광물의 개수를 곡갱이 수에 맞게 삭제한다.
2. 5그룹으로 묶고 피로도를 기준으로 내림차순으로 정렬한다
3. 첫 번째(가장 높은 피로도를 가진 그룹)를 선택한다. 가장 좋은(다이아몬드 > 철 > 돌) 곡갱이를 고른다.
4. 두 번째, 세 번 째 ~ .... 나머지도 마찬가지도

결국, 졍렬 후 현재 상황에서 가장 좋은 곡갱이를 고르는 거므로 그리드 알고리즘이다.

코드

import java.util.*;

class Solution {
    
    List<String> mlist;
    int allN;
    
    public int solution(int[] picks, String[] minerals) {
    
        allN = picks[0] + picks[1] + picks[2];
        
        mlist = new ArrayList<>(Arrays.asList(minerals));
        decideMineralSize();
        
        ArrayList<int[]> list = initFatiques();
        Collections.sort(list, ((o1,o2) ->  o2[3] - o1[3]));
        
        
        int pInd =0;    
        int fatigue = 0;

        for(int i =0; i < list.size();  i++) {
            if(picks[pInd] != 0) {
                if(pInd == 0) 
                    fatigue += list.get(i)[0] + list.get(i)[1] + list.get(i)[2] ;
                else if(pInd == 1)
                     fatigue += 5*list.get(i)[0] + list.get(i)[1] + list.get(i)[2];
                else if(pInd == 2)
                     fatigue += 25*list.get(i)[0] + 5*list.get(i)[1] + list.get(i)[2];
                picks[pInd]--;
            }
            if(picks[pInd] == 0)
                pInd++;
        }
            return fatigue;
        
    }
    
    private void decideMineralSize() {
        if(mlist.size() > allN*5) {
          int gap = mlist.size() - (allN*5);
          for(int i= 0; i < gap; i++) {
            mlist.remove(mlist.size() -1 - i);
          }
        } 
    }
    private ArrayList<int[]> initFatiques() {
        ArrayList<int[]> list = new ArrayList<int[]>(); 
        int mInd = 0;
        
        for(int i = 0; i < Math.ceil((double)mlist.size()/5); i++) {
            int[] j = {0,0,0,0};
            list.add(j);    
        } //list 초기화
        
        for(int i = 0; i < mlist.size(); i++) {
                
                if(mlist.get(i).equals("diamond"))
                   list.get(mInd)[0]++; 
                else if(mlist.get(i).equals("iron")) 
                   list.get(mInd)[1]++; 
                else if(mlist.get(i).equals("stone"))
                   list.get(mInd)[2]++;

                if( ((i+1)%5 == 0) || i+1 == mlist.size()) { //5개 원소 탐색 또는 끝까지 탐색했으면 미네랄 가중치 계산
                    list.get(mInd)[3] = 25*list.get(mInd)[0] + 5*list.get(mInd)[1] + list.get(mInd)[2];
                    mInd++;
                }
            
        }
        
        return list;
        
    }
}

pInd를 올리는 부분(곡갱이를 다른 걸로 선택)하는 부분이 잘못되어있다. 현재 코드에서는 반복문의 뒷부분에 선언되어있는데 앞부분에서 곡갱이가 1개이상 있는 곡갱이를 선태하도록 코드를 바꿔보겠다.

또한 변수명이나 함수명을 의도에 맞게 바꿔보겠다.

2번째 시도

import java.util.*;

class Solution {
    
    List<String> mineralsList;
    int totalPicks;
    
    public int calculateFatigue(int[] picks, String[] minerals) {
    
        totalPicks = picks[0] + picks[1] + picks[2];
        
        mineralsList = new ArrayList<>(Arrays.asList(minerals));
        filterMineralsByPicks();
        
        ArrayList<int[]> mineralStats = calculateMineralStats();
        Collections.sort(mineralStats, ((o1,o2) ->  o2[3] - o1[3]));
        
        int pickIndex = 0;    
        int fatigue = 0;
        
        for(int i = 0; i < mineralStats.size();  i++) {
            while(picks[pickIndex] == 0) {
                pickIndex++;
            }
          
            if(picks[pickIndex] != 0) {
                if(pickIndex == 0) {
                    fatigue += mineralStats.get(i)[0] + mineralStats.get(i)[1] + mineralStats.get(i)[2];
                }
                else if(pickIndex == 1){
                    fatigue += 5 * mineralStats.get(i)[0] + mineralStats.get(i)[1] + mineralStats.get(i)[2];
                }
                else if(pickIndex == 2) {
                    fatigue += 25 * mineralStats.get(i)[0] + 5 * mineralStats.get(i)[1] + mineralStats.get(i)[2];
                }
                picks[pickIndex]--;
            }
        }
        
        return fatigue;
    }
    
    private void filterMineralsByPicks() {
        if(mineralsList.size() > totalPicks * 5) {
            int excess = mineralsList.size() - (totalPicks * 5);
            for(int i = 0; i < excess; i++) {
                mineralsList.remove(mineralsList.size() - 1 - i);
            }
        }
    }
    
    private ArrayList<int[]> calculateMineralStats() {
        ArrayList<int[]> mineralStats = new ArrayList<int[]>(); 
        int mineralIndex = 0;
        
        for(int i = 0; i < Math.ceil((double)mineralsList.size() / 5); i++) {
            int[] stats = {0, 0, 0, 0};
            mineralStats.add(stats);    
        } // Initialize the list
        
        for(int i = 0; i < mineralsList.size(); i++) {
            if(mineralIndex < mineralStats.size()) {
                if(mineralsList.get(i).equals("diamond"))
                    mineralStats.get(mineralIndex)[0]++; 
                else if(mineralsList.get(i).equals("iron")) 
                    mineralStats.get(mineralIndex)[1]++; 
                else if(mineralsList.get(i).equals("stone"))
                    mineralStats.get(mineralIndex)[2]++;
                
                if(((i + 1) % 5 == 0) || i + 1 == mineralsList.size()) { // Calculate mineral weight after every 5 elements or at the end
                    mineralStats.get(mineralIndex)[3] = 25 * mineralStats.get(mineralIndex)[0] + 5 * mineralStats.get(mineralIndex)[1] + mineralStats.get(mineralIndex)[2];
                    mineralIndex++;
                }
            }
        }
        
        return mineralStats;
    }
}

테스트 1번과 테스트 16번이 통과가 안됐다.

mineralsList.remove(mineralsList.size() - 1 -i);

이부분이 문제가 있다. 가장 끝에 있는 광물들을 업애고 싶은 의도였는데 이코드는 항상 맨 마지막 광물을 없애는 게 아니다 수정해보겠다.

3번째 시도

import java.util.*;

class Solution {
    
    List<String> mineralsList;
    int totalPicks;
    
    public int solution(int[] picks, String[] minerals) {
    
        totalPicks = picks[0] + picks[1] + picks[2];
        
        mineralsList = new ArrayList<>(Arrays.asList(minerals));
        filterMineralsByPicks();
        
        ArrayList<int[]> mineralStats = calculateMineralStats();
        Collections.sort(mineralStats, ((o1,o2) ->  o2[3] - o1[3]));
        
        int pickIndex = 0;    
        int fatigue = 0;
        
        for(int i = 0; i < mineralStats.size();  i++) {
            while(picks[pickIndex] == 0) {
                pickIndex++;
            }
          
            if(picks[pickIndex] != 0) {
                if(pickIndex == 0) {
                    fatigue += mineralStats.get(i)[0] + mineralStats.get(i)[1] + mineralStats.get(i)[2];
                }
                else if(pickIndex == 1){
                    fatigue += 5 * mineralStats.get(i)[0] + mineralStats.get(i)[1] + mineralStats.get(i)[2];
                }
                else if(pickIndex == 2) {
                    fatigue += 25 * mineralStats.get(i)[0] + 5 * mineralStats.get(i)[1] + mineralStats.get(i)[2];
                }
                picks[pickIndex]--;
            }
        }
        
        return fatigue;
    }
    
    private void filterMineralsByPicks() {
        if(mineralsList.size() > totalPicks * 5) {
            int excess = mineralsList.size() - (totalPicks * 5);
            for(int i = 0; i < excess; i++) {
                mineralsList.remove(mineralsList.size() - 1);
            }
        }
    }
    
    private ArrayList<int[]> calculateMineralStats() {
        ArrayList<int[]> mineralStats = new ArrayList<int[]>(); 
        int mineralIndex = 0;
        
        for(int i = 0; i < Math.ceil((double)mineralsList.size() / 5); i++) {
            int[] stats = {0, 0, 0, 0};
            mineralStats.add(stats);    
        } // Initialize the list
        
        for(int i = 0; i < mineralsList.size(); i++) {
            if(mineralIndex < mineralStats.size()) {
                if(mineralsList.get(i).equals("diamond"))
                    mineralStats.get(mineralIndex)[0]++; 
                else if(mineralsList.get(i).equals("iron")) 
                    mineralStats.get(mineralIndex)[1]++; 
                else if(mineralsList.get(i).equals("stone"))
                    mineralStats.get(mineralIndex)[2]++;
                
                if(((i + 1) % 5 == 0) || i + 1 == mineralsList.size()) { // Calculate mineral weight after every 5 elements or at the end
                    mineralStats.get(mineralIndex)[3] = 25 * mineralStats.get(mineralIndex)[0] + 5 * mineralStats.get(mineralIndex)[1] + mineralStats.get(mineralIndex)[2];
                    mineralIndex++;
                }
            }
        }
        
        return mineralStats;
    }
}

저작자표시

'알고리즘' 카테고리의 다른 글

2개 이하로 다른 비트 / 자바 / 프로그래머스 (0)	2024.04.14
항해 99 17일차 TIL ( JadenCase 문자열 만들기 / 프로그래머스) (0)	2024.04.14
항해 99 15일차 TIL ( 뒤에 있는 큰 수 찾기 / 프로그래머스) (0)	2024.04.12
항해 99 13일차 TIL( 덧칠하기 / 프로그래머스) (0)	2024.04.09
항해99 11일차 TIL(피로도 / 프로그래머스) (0)	2024.04.06

아무튼, 쓰기

항해 99 16일차 TIL( 광물캐기 / 프로그래머스)

문제

1번째 시도

2번째 시도

3번째 시도

'알고리즘' 카테고리의 다른 글

티스토리툴바

항해 99 16일차 TIL( 광물캐기 / 프로그래머스)

문제

1번째 시도

2번째 시도

3번째 시도

'알고리즘' 카테고리의 다른 글

관련글

티스토리툴바