99클럽 코테 스터디 2일차 TIL + 해시(분류된 의상)

오늘의 과제

프로그래머스 Lv.2 해시로 분류된 의상입니다.

 

기억에는 없으나 예전에 풀었던 문제로 복기겸 다시 풀어봅니다.

 

문제

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

프로그래머스

 

 

먼저 문제 종류인 "해시"에서 힌트를 얻어 Map으로 접근하였습니다.

 

문제에서는 각 종류별로 한 가지씩 선택하거나 선택하지 않는 모든 조합의 수를 계산하되,

반드시 최소 한 가지 이상의 옷은 입어야 한다는 조건이 있습니다.

 

여기서 "선택하거나 선택하지 않는" 이 키 포인트가 될 것 같은데

 

예제 입력 1번을 예시로 들어 보겠습니다.

 

0번 인덱스는 의상의 이름, 1번 인덱스가 종류이니 헤드기어 둘, 아이웨어 하나가 입력으로 들어왔네요.

 

실제 종류별 카운트는 둘, 하나가 맞으나 헤드기어에서 선택했다면 아이웨어는 선택하지 않을 수 있습니다.

 

즉, 종류별 개수 + 1이 실제 조합할 수 있는 의상의 수가 되기 때문에 모든 조합의 수는

각 종류별 개수 + 1을 모두 곱해주면 됩니다.

 

입력의 크기가 작으니 조건처럼 이해를 위해 하나한 풀어봅니다.

 

[yellow_hat]

[blue_sunglasses]

[green_turban]

[yellow_hat, blue_sunglasses]

[green_turban, blue_sunglasses]

 

어? 헤드기어가 둘, 아이웨어가 하나면 각 종류에 1씩 더했을 때 3 * 2이니 6이 아닌가?

 

라고 생각하셨다면 문제의 조건을 다시 확인해보겠습니다.

옷은 안입어도 안경이라도 써야하는 멋쟁이 변태

 

네. 위에 서술했듯 최소 한 개의 의상을 입어야 하기 때문에 조합의 수인 6에서 1을 빼줘야 정답이 됩니다.

 

아래는 풀이 코드입니다.

import java.util.*;

class Solution {
    public int solution(String[][] clothes) {
        int answer = 1;
        
        // 1. 종류별 한 가지만 착용할 수 있음.
        // 2. 이미 착용했던 종류를 또 착용하더라도 다른 종류를 더하거나 덜하면 착용 가능
        // 3. 최소 한 개는 입어야 함.
        
        // 종류별 총 합은 최소 가지 수
        // 안입을 수 있으니 종류별 가지 수 + 1
        // 최소 한 개는 입어야 하니 최종 카운트 - 1
        
        HashMap<String, Integer> map = new HashMap<>();
        // 0번 인덱스가 의상 이름, 1번 인덱스가 의상의 종류
        for (String[] s : clothes) {
            map.put(s[1], map.getOrDefault(s[1], 0) + 1);
        }
        
        for (String s : map.keySet()) {
            answer *= map.get(s) + 1;
        }
        return answer - 1;
    }
}

 

 

 

배운점

글 초반에 언급했듯 사실 이미 풀어본 문제이며 "해시"라는 힌트가 이미 나와있었기 때문에 쉽게 풀었던 문제입니다.

 

이미 풀어본 문제 + 힌트라면 뚝딱뚝딱 풀어야 맞겠지만 오랫만에 코테 공부인지라

위에서 언급한 강조 포인트에서 살짝 헤맸습니다.

 

특정 로직이나 알고리즘 기술이 들어간 문제는 아니기에 기술상으로는 배운 점은 없다고 할 수 있으나

다시 코테를 준비하는 입장에서 잊었던 한 가지를 상기했습니다.

 

알고리즘은 닥치고 꾸준함이다.