99클럽 코테 스터디 39일차 TIL , 광물 캐기

 

문제

풀이

다이아, 철, 돌 곡괭이가 있다. 광물에는 다이아, 철, 돌이 있다.

다이아 > 철 > 돌 순으로 곡괭이가 강력해서 다이아는 모든 광물을 피로도 1로 캐낼 수 있다. 철은 다이아는 5 나머지는 1의 피로도로 광물을 캘 수 있다. 돌은 다이아는 25 철은 5 돌은 1의 피로도로 캐낼 수 있다.

한번 사용하기 시작한 곡괭이로는 무조건 5개의 광물을 캐내야 종료된다.

 

입력으로 다이아, 철, 돌 곡괭이의 개수와 캐야 하는 광물이 주어질 때 가장 적은 피로도로 광물을 캐내는 경우를 출력하면 된다.

 

제출 1 - 정답

class Solution {
    private int answer;
    private List<int[]> caseList;
    private int[] pick;
    public int solution(int[] picks, String[] minerals) {
        int dia = 0;	//다이아면 피로도가 얼마나 필요하지
        int iron = 0;	//철이면 피로도가 얼마나 필요하지
        int stone = 0;	//돌이면 피로도가 얼마나 필요하지

        answer = Integer.MAX_VALUE;	//최소값을 찾기위해
        caseList = new ArrayList<>();	//모든 경우를 넣어 놓기 위해
        pick = picks;	//클래스 변수로 선언

        int picksLength = (picks[0] + picks[1] + picks[2]) * 5;	//몇개 까지 캘 수 있는지

        int i=0;
        while(i < picksLength && i<minerals.length){
            if(minerals[i].equals("diamond")){	//광물이 다이아면
                dia += 1;
                iron += 5;
                stone += 25;
            }else if(minerals[i].equals("iron")){	//광물이 철이면
                dia += 1;
                iron += 1;
                stone += 5;
            }else if(minerals[i].equals("stone")){	//광물이 돌이면
                dia += 1;
                iron += 1;
                stone += 1;
            }
            if(i%5 == 4){	//기준 5마다 저장
                caseList.add(new int[]{dia, iron, stone});
                dia = 0;
                iron = 0;
                stone = 0;
            }

            i++;
        }

        if(dia != 0){	// 남는게 있으면 넣어줌
            caseList.add(new int[]{dia, iron, stone});
        }

        int[] visited = new int[caseList.size()];	//방문 했었고 뭘로 방문 했는지
        int[] visitedCase = new int[caseList.size()];	//값이 몇인지

        dfs(visited, visitedCase, 0);

        return answer;
    }

    private void dfs(int[] visited, int[] visitedCase, int depth){
        if(depth == caseList.size()){	//다 골랐으면
            int dia = 0;
            int iron = 0;
            int stone = 0;
            int cnt = 0;
            for(int i=0;i<depth;i++){	//광물 개수 세기
                if(visited[i] == 1) dia++;
                else if(visited[i] == 2) iron++;
                else if(visited[i] == 3) stone++;

                cnt += visitedCase[i];	// 전체 피로도 저장
            }

			//광물이 모자라면 return
            if(dia > pick[0] || iron > pick[1] || stone > pick[2]) return;
            answer = Math.min(answer, cnt);

            return;
        }

        int[] tmp = caseList.get(depth);	
        for(int i=0;i<3;i++) {
            visited[depth] = i + 1;
            visitedCase[depth] = tmp[i];
            dfs(visited, visitedCase, depth + 1);
        }
    }
}

 

각 광물마다 각 곡괭이로 캐면 얼마나 걸리는지 더 한 후에 각 조건에 맞는 경우를 선택하는 dfs를 돌려서 정답을 선택했다.

각 자리마다 곡괭이를 선택하고 만약 곡괭이가 모자라면 return 한다.

이렇게 만들어주기 위해 visited도 boolean이 아닌 int로 0인경우 다이아, 철, 돌 인경우로 나누었고 개수도 넣기 위해 하나의 매개변수를 더 만들었다.

자세한 설명은 코드의 주석을 보면 된다.

TIL

• 아주 큰일이 있었다. 위와 같은 풀이는 제 한 시간 안에 찾았는데 인텔리제이에서는 정답이 나오는데 프로그래머스에서는 위에서 주어진 간단한 예제마저 통과를 못하는 것이다. 질문을 남겼지만 답이 없다가 스터디모임 중에 어떤 챌린저 분께서 찾아주셨다.
• 자바의 문자열 비교를 '=='를 사용해서 하고있었다... 
  • 자바에서는 문자열을 equlas() 사용하는데 이것은 왜 그럴까? 자바의 메모리 관리 방식은 문자열 상수풀 때문이다. 자바에서는 새로운 문자열 리터럴 생성 시 문자열상수풀에 문자열을 저장한다. 그렇기 때문에 같은 문자열을 생성하는 것처럼 보여도 같은 경우가 생기는 것이다.
  • 하지만 new String()처럼 새로운 객체를 생성하면 새롭게 저장된다. 즉, 인스턴스 생성시  힙메모리에 저장되기 때문에 ==로 참조값 비교 시에 다른 것이라고 나오는 것이다.
• 결론 문자열 비교 조심하자!