[프로그래머스] 의상 (자바)

프로그래머스 고득점 Kit: 해시 - 의상

문제 설명

"의상" 문제는 주어진 의상 목록을 통해 서로 다른 조합으로 입을 수 있는 경우의 수를 구하는 문제입니다. 각 의상은 특정 종류(예: headgear, eyewear)로 분류되며, 한 종류의 의상은 한 번에 하나만 착용할 수 있습니다. 최소 한 개의 의상을 착용해야 합니다.

문제 접근 방법

1. HashMap 사용: 의상의 종류를 키(key)로, 해당 종류의 의상 개수를 값(value)으로 하는 HashMap을 사용합니다.
2. 의상 종류별 개수 계산: 의상 목록을 순회하며 각 의상 종류의 개수를 HashMap에 저장합니다.
3. 조합 계산: 의상 종류별로 (해당 종류의 의상 개수 + 1)을 모두 곱한 후 1을 뺍니다. 여기서 1을 더하는 이유는 해당 종류의 의상을 착용하지 않는 경우를 포함하기 위함입니다. 마지막에 1을 빼는 이유는 모든 종류의 의상을 착용하지 않는 경우를 제외하기 위함입니다.

시간 복잡도 분석

• 의상의 수를 N이라고 할 때, 시간 복잡도는 O(N)입니다.
  • 의상 목록을 처리하는데 O(N)
  • HashMap을 순회하는데 O(N)

따라서 전체 시간 복잡도는 O(N)입니다.

해결 방법

아래는 주어진 문제를 해결하는 Java 코드입니다:

package psg.고득점킷트.해시;

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

public class PSG_의상 {
    public static void main(String[] args) {
        String[][] clothes = {{"yellow_hat", "headgear"}, {"blue_sunglasses", "eyewear"}, {"green_turban", "headgear"}};
        PSG_의상 psg_의상 = new PSG_의상();
        System.out.println(psg_의상.solution(clothes));
    }

    public int solution(String[][] clothes) {
        Map<String, Integer> map = new HashMap<>();
        for (String[] clothe : clothes) {
            map.put(clothe[1], map.getOrDefault(clothe[1], 0) + 1);
        }
        int result = 1;
        for (String key : map.keySet()) {
            result = result * (map.get(key) + 1);
        }
        return result - 1;
    }
}