프로그래머스 level2 - 위장

programmers.co.kr/learn/courses/30/lessons/42578

코딩테스트 연습 - 위장

1. 유형

해시

 

2. 풀이

처음에 2가지 방법으로 풀어보았다.

 

우선 잘못된 방법.

재귀함수 사용해서 조합을 구함.

 

이 문제를 combination으로 구할 경우 94점이 나옴. 1번에서 시간 초과가 나옵니다.

 

따라서, 이 문제는 수학적 지식으로 풀어야합니다.

 

즉 1번 예제에서, 헤드기어2개, 안경1개 인 경우

 

(2+1) * (1+1) -1 로 풀면 답이 나옵니다.

 

해드기어2개에 왜 1을 더했냐?

 

해드기어 2개 선택하는 경우의 수 + 선택을 한개도 안하는 경우의 수 = 3

 

식의 맨 마지막에 -1을 해주는 이유?

 

전부다 선택을 안 하는 경우의 수 빼주기.

 

3. 코드

잘못된 풀이. 조합 사용 ->효율성 1개 통과 못함

import java.util.*;
class Solution {
    static int size, count;
    static String[][] clothe;
    static HashMap<String, Boolean> type;
    static HashMap<String, String> hm;
    static void dfs(int idx, int select){
        if(idx == size && select>0){
            count++;
            return;
        }
        if(idx == size)
            return;
        String temp = hm.get(clothe[idx][0]);
        if(type.get(temp) == false){
            type.put(temp, true);
            dfs(idx+1, select+1);
            type.put(temp, false);
        }
        dfs(idx+1, select);
    }
    public int solution(String[][] clothes) {
        int answer = 0;
        count = 0;
        size = clothes.length;
        type = new HashMap<>();
        clothe = clothes;
        hm = new HashMap<>();
        for(int i=0; i<size; i++){
            hm.put(clothes[i][0], clothes[i][1]);
            type.put(clothes[i][1], false);
        }
        dfs(0, 0);
        answer = count;
        return answer;
    }
}

 

올바른 코드.

import java.util.*;
class Solution {
    static HashMap<String, Integer> map;
    public int solution(String[][] clothes) {
        int answer = 0;
        map = new HashMap<>();
        int size = clothes.length;
        int mul=1;
        for(int i=0; i<size; i++){
            int num = map.getOrDefault(clothes[i][1], 0);
            map.put(clothes[i][1], ++num);
        }
        Set<String> keys = map.keySet();
        for(String type : keys){
            int temp = map.get(type);
            System.out.println(temp);
            mul*=(temp+1);
        }
        answer = mul-1;
        return answer;
    }
}

 

4. 새로운 지식

 

키를 찾으려면 HashMap의 keySet()을 써야한다.

 

그냥 for-each문으로 돌리니 키만 따로 못 찾는다고 나옴.

 

또하나,

 

Map인터페이스에서 getOrDefault(키, 0일때 리턴값) 이라는 함수가 있다.

 

정말 편하다. 원래는 containsKeys()로 키가 있는지를 찾아봐야 하는데, if문을 줄일 수 있어서 편리한 함수다.