(알고리즘 스터디) 4주차 수 _ 해시맵🔐 _ (Programmers) 위장

🌟 프로그래머스 / 해시 / Level2 / 위장

📃 문제

프로그래머스

🚫 제한 사항

• clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
• 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.
• 같은 이름을 가진 의상은 존재하지 않습니다.
• clothes의 모든 원소는 문자열로 이루어져 있습니다.
• 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.
• 스파이는 하루에 최소 한 개의 의상은 입습니다.

👀 입출력 예

clothes	return
[["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]]	5
[["crow_mask", "face"], ["blue_sunglasses", "face"], ["smoky_makeup", "face"]]	3

🤔 풀이 방법

1️⃣  방법 (1) : Map 으로 종류별 개수 확인 후 조합 사용

① 사고 과정

/*
풀이 방법
(1) 변수
a) Map -> key : (String) 종류 / value : (int) 개수
(2) 종류 파악 -> key
a) split("_") 수행
    가) 첫번째 원소 : 이름
    나) 두번쨰 원소 : 종류
b) a-나) 의 종류가 key 에 있는지 확인 (if 문)
    가) true : 개수 ++ 해서 업데이트
    나) false : 개수 1로 해서 추가 (add)
(3) 경우의 수 환산
a) value set 반환
b) max 값 확인
c) 1-max 까지 경우의 수 확인
    ex) 모자 : 2개, 선글라스 : 1개, 바지 2개
        가) max : 2개
        나) 1개의 경우 : 2 + 1 + 2 = 5
        다) 2개의 경우 : 2 * 1 + 2 * 2 + 1 * 2 = 8
    ➡️ 조합으로 가야한다. / 완성될 때 마다 곱을 answer 에 더하는 방식
*/

➡️ 예시 : 아래와 같이 종류별로 개수를 확인하여 조합을 구하고자 했다.

주어진 배열 : [["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]]
생성된 Map 형태 ➡️ entrySet() 호출시
[eyewear=1, headgear=2]

② 구현 코드

import java.util.Map;
import java.util.Set;
import java.util.HashMap;

class Solution {
    public static int[] counts;
    public static int answer = 0;
    
    public int solution(String[][] clothes) {
        
        // Map 생성
        Map<String, Integer> map = new HashMap<>();
        
        // 배열 분리
        for (String[] clothe : clothes) {
            String type = clothe[1];
            
            // map 에 삽입
            int count = 0;
            if (map.containsKey(type)) {
                count = map.get(type);
            }
            map.put(type, ++count);
        }
        
        // // 정상적으로 담겼는지 확인
        // System.out.println(map.entrySet());
        
        // 경우의 수 확인 (1)
        String[] types = map.keySet().toArray(new String[map.size()]);
        counts = new int[map.size()];
        
        for (int i=0; i<types.length; i++) {
            counts[i] = map.get(types[i]);
        }
        // 경우의 수 확인 (2) 조합
        for (int r=1; r <= counts.length; r++) {
             Comb(new boolean[counts.length], 0, r, 1);
            
            System.out.println(r);
        }
        return answer;
    }
    
    // 조합
    public static void Comb (boolean[] visited, int start, int r, int total) {
        if (r==0) {
            answer += total;
            return;
        }
        for (int i=start; i<counts.length; i++) {
            // 방문
            visited[i] = true;
            total *= counts[i];
            // 재귀
            Comb(visited, i+1, r-1, total);
            // 복구
            total /= counts[i];
            visited[i] = false;
        }
    }
}

③ 결과

테스트 케이스 1번 실패 (시간초과)

➡️ 30개의 테스트 중 29개를 통과하고 1개를 시간초과로 실패하였다. 확인해보니 첫번째 테스트는 서로 다른 종류가 30개인 상태라고 한다. 결론적으로 마지막에 조합으로 푸는 것은 불가능하다는 것으로 해석할 수 있다.

2️⃣  방법 (2) : Map 으로 종류별 개수 확인 후 조합 사용 but 조합을 직접적으로 구현하지는 않음

➡️ 앞선 문제를 해결하는 방법은 사실 수학적인 문제라 자세히 정리하지는 않으려고 한다. 개념은 아래와 같다.

 

① 개념

Point : 조합을 사용하지 않아야함
➡️ (각 옷 개수 + 안입는 경우) 를 다 곱하고 마지막에 -1 (모두 안입는 경우)
ex) 모자 2개 & 선글라스 1개 => (2+1) * (1*1) -1 = 5

위 개념에 따라 기존 코드에서 조합 함수를 빼고 단순히 수를 계산하도록 하였다.

 

② 구현 코드

import java.util.Map;
import java.util.Set;
import java.util.HashMap;
class Solution {
    public int solution(String[][] clothes) {
        int answer = 1;
        
        // Map 생성
        Map<String, Integer> map = new HashMap<>();
        
        // 배열 분리
        for (String[] clothe : clothes) {
            String type = clothe[1];
            
            // map 에 삽입
            int count = 0;
            if (map.containsKey(type)) {
                count = map.get(type);
            }
            map.put(type, ++count);
        }
        
        
        // 경우의 수 확인 (1)
        String[] types = map.keySet().toArray(new String[map.size()]);
        int[] counts = new int[map.size()];
        
        for (int i=0; i<types.length; i++) {
            counts[i] = map.get(types[i]);
        }
        
        // 경우의 수 확인 (2)
        for (int n : counts) {
            answer *= n+1;
        }
        
        return --answer;
    }
}

③ 결과

통과

➡️ 1번 테스트 케이스도 잘 통과하였고, 전체적으로 시간도 줄어들었다. 하지만 자료구조를 잘 활용해서라기 보다는 단순 수학문제라 큰 의미는 없는 것 같다.

3️⃣  방법 (3) : 스터디 후 방법(2) 코드 개선

➡️ 방법 (2) 를 풀이하면서 개선하고 싶었던 부분은 각 종류별 개수를 확인하기 위해 배열을 선언하고 key Set 에서 하나씩 빼오는 과정이었다. 해당 부분을 스터디를 진행하면서 개선점을 확인할수 있었다. 추가로 초반에 Map 에서 중복 여부를 확인하고 개수 정보를 다르게 하는 과정에서도 개선점을 알 수 있었다.

 

① Map 에 정보를 넣는 과정 : Map.getOrDefault() 활용

리턴값 : default V
메서드 : getOrDefault(Object key, V defaultValue)
➡️ 지정된 키가 매핑된 값을 반환하거나, 맵에 키에 대한 매핑이 없는 경우 defaultValue 를 반환

// 기존 코드

for (String[] clothe : clothes) {
    String type = clothe[1];

    // map 에 삽입
    int count = 0;
    if (map.containsKey(type)) {
        count = map.get(type);
    }
    
    map.put(type, ++count);
}

// 개선 코드

// 배열 분리
for (String[] clothe : clothes) {
    String type = clothe[1];
    
    map.put(type, map.getOrDefault(type, 0)+1);
}

➡️ 성능면에서 엄청난 개선이 있는건 아니지만, 조건문도 없어지고 전체적인 코드 수도 줄었기 때문에 가독성이 높아진 것 같다.

 

② 종류별 개수를 확인하는 과정 : 향상된 for 문 & Map.values() 활용

// 기존 코드

// key Set 을 배열로 변환
String[] types = map.keySet().toArray(new String[map.size()]);
// vlaue 값들을 담기 위한 배열 선언
int[] counts = new int[map.size()];

// key 배열 & value 배열을 순회하며 value 값 담음
for (int i=0; i<types.length; i++) {
    counts[i] = map.get(types[i]);

// 경우의 수 확인
for (int n : counts) {
    answer *= n+1;
}

// 개선 코드

// 방법 (1) : 향상된 for 문 활용
for (String type : map.keySet()) {
    answer *= map.get(type) + 1;
}

// 방법 (2) : Map.values() 활용
for (int count : map.values()) {
	answer *= count + 1;
}

➡️ 가독성은 기본이고, 불필요한 선언도 2개나 줄였다. 메모리 차지에도 효율적일 것 같다.

💻 풀이 코드

import java.util.Map;
import java.util.Set;
import java.util.HashMap;

class Solution {
    public int solution(String[][] clothes) {
        int answer = 1;
        
        // Map 생성
        Map<String, Integer> map = new HashMap<>();
        
        // 배열 분리
        for (String[] clothe : clothes) {
            String type = clothe[1];

            // map 에 삽입
            map.put(type, map.getOrDefault(type, 0)+1);
        }
        
        // 경우의 수 확인
        for (int count : map.values()) {
    	answer *= count + 1;
        }
        
        // 아무것도 입지 않은 경우 1개 빼기
        return --answer;
    }
}

[level 2] Title: 위장, Time: 0.07 ms, Memory: 89.1 MB -BaekjoonHub · Young998904/Practice_Algorithm_Auto@9df2d7f