[프로그래머스] 의상 문제 (Java Hash 풀이)

안녕하세요, 스코리아입니다.

오늘은 자바(Java)의 Hash(해시)를 이용한 프로그래머스 Lv.2 의상 문제를 풀어보겠습니다.

 

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/42578

프로그래머스

• 각 종류별로 최대 1가지 의상만 착용 가능
• 착용할 수 있는 의상의 경우의 수를 구하는 문제
• 아예 옷을 안 입는 경우는 없음 (최소 1개의 의상은 입음)
• [의상의 이름, 의상의 종류]로 이루어진 clothes 배열이 주어짐
• 같은 이름을 가진 의상은 존재하지 않음

프로그래머스 문제 - 의상

문제에 나와있는 예시를 토대로 설명해 보겠습니다.

clothes (옷)	return (경우의 수)
[["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]]	5

• 의상의 종류에 따라 분류에 해보기: "headgear"에 해당하는 의상이 yellow_hat, green_turban이고 "eyewear"에 해당하는 의상이 blue_sunglasses이므로 아래와 같이 5개의 조합이 가능

1. yellow_hat
2. blue_sunglasses
3. green_turban
4. yellow_hat + blue_sunglasses
5. green_turban + blue_sunglasses

• 경우의 수만 구하면 되는 문제로, 의상의 종류에 따른 의상 개수는 중요하지만 의상의 이름은 중요하지 않습니다.

---

풀이 과정

우선 다음과 같은 경우를 생각해 봅시다.

• "headgear"에 의상이 2개, "eyewear"에 의상이 3개, "face"에 의상이 4개 있다고 합니다.
• 우리는 해당 의상 종류의 의상을 입지 않는 경우도 생각해야 합니다.
• 경우의 수를 구하기 위해 "안 입는 경우"를 1개의 경우로 생각하여  의상의 종류에 따른 의상의 개수에 1씩 더해줍니다.
• 그러면 각각 3, 4, 5가 될 것입니다.
• 3*4*5 = 60으로 경우의 수를 구합니다. 다만, 여기서 의상을 아예 안 입는 경우는 없으니 -1을 해주어야 합니다.
• 따라서 60-1 = 59가 정답이 됩니다.

위의 예시를 토대로 설명한 대로, HashMap을 이용하여 풀이하였습니다.

import java.util.*;

class Solution {
    public int solution(String[][] clothes) {
        int answer = 1;
        HashMap<String, Integer> map = new HashMap<>();
        
        for(String c[] : clothes){
            map.put(c[1], map.getOrDefault(c[1], 0) + 1);
        }
        
        /**
        headgear
            2개 + 안입는경우 = 3
        eyewear
            3개 + 안입는경우 = 4
        face
            4개 + 안입는경우 = 5
        => 3*4*5
        */
        for(String s : map.keySet()){
            answer *= map.get(s) + 1; // 안입는 경우 + 1
        }
        
        return answer-1; // 아예 안입는 경우는 없으니, -1
    }
}

1. key 값은 의상 종류의 이름(String)을, value 값에는 의상 종류에 따른 의상의 개수(Integer)를 저장하는 HashMap을 생성하였습니다.
2. clothes 배열에 대해 for문을 돌려서, c[1] (의상 종류 이름)을 key 값으로 하고, 의상 종류가 없으면 1을 넣고, 의상 종류가 있으면 그 값에 1을 더해서 넣었습니다.
3. map.keySet()을 이용하여 map에 대한 for문을 돌리고 해당 value 값에 안 입는 경우의 수 1개를 더하여 answer에 누적적으로 곱해주었습니다.
4. 마지막으로 아무것도 안 입는 경우는 없으므로 answer에 1을 빼주었습니다.

 

실행 결과

프로그래머스 문제 실행결과 - 의상

• 대부분의 테스트는 0~1ms 정도로, 비교적 빠른 모습입니다.

 

---

지금까지 자바(Java) 해시를 이용한 프로그래머스 '의상' 문제에 대해서 알아보았습니다.

읽어주셔서, 감사합니다.