[Java]백준9375-패션왕 신해빈

난이도는 실버3, 조합과 해시맵을 이용하는 문제다.

문제는 아래와 같다.

https://www.acmicpc.net/problem/9375

---

문제

해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경대신 렌즈를 착용하거나 해야한다. 해빈이가 가진 의상들이 주어졌을때 과연 해빈이는 알몸이 아닌 상태로 며칠동안 밖에 돌아다닐 수 있을까?

입력

첫째 줄에 테스트 케이스가 주어진다. 테스트 케이스는 최대 100이다.

• 각 테스트 케이스의 첫째 줄에는 해빈이가 가진 의상의 수 n(0 ≤ n ≤ 30)이 주어진다.
• 다음 n개에는 해빈이가 가진 의상의 이름과 의상의 종류가 공백으로 구분되어 주어진다. 같은 종류의 의상은 하나만 입을 수 있다.

모든 문자열은 1이상 20이하의 알파벳 소문자로 이루어져있으며 같은 이름을 가진 의상은 존재하지 않는다.

출력

각 테스트 케이스에 대해 해빈이가 알몸이 아닌 상태로 의상을 입을 수 있는 경우를 출력하시오.

예제 입력 

2
3
hat headgear
sunglasses eyewear
turban headgear
3
mask face
sunglasses face
makeup face

예제 출력 

5
3

힌트

첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로   (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다.

 

---

접근

1. 우선 해시맵을 이용해 의상과 종류를 입력 받는다.

2. 중복을 제거하는 경우의 수를 구한다...인데

 

조금더 쉽게 접근하기 위해 어떻게 조합을 해야하는지 먼저 알아보자.

먼제 각 의상을 입는 경우의 수를 구한다.

 

• 모자: 2개 (A, B) → 경우의 수: 3개 (A, B, 안 씀)
• 안경: 1개 (C) → 경우의 수: 2개 (C, 안 씀)

둘을 곱해서 경우의 수를 구하는데,  "아무것도 입지 않는 경우"를 제외해야 한다.

즉, 최종 공식은

(종류1의경우의수)×(종류2의경우의수)×⋯−1

따라서 경우의 수를 계산하기 위해 해시맵으로 <String 종류(하나만 가능), Integer 의상(중복된 개수 카운트)>

종류를 키로 하고, 의상을 카운트 하기로 했다. 

처음 작성한 코드는 아래와 같다.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) { // 의상 개수
            int k = sc.nextInt();
            Map<String, Integer> cloth = new HashMap<>();
            for (int j = 0; j < k; j++) {
                sc.next();
                String next = sc.next(); // 종류
                if (cloth.containsKey(next)) { // 키가 중복일떼
                    cloth.replace(next, cloth.get(next) + 1);
                } else {
                    cloth.put(next, 2); // 입지 않는 경우도 고려
                }
            }
            int result = 1;
            for (int value : cloth.values()) {
                result *= value; // 경우의 수를 곱해줌
            }
            System.out.println(result - 1); // 아무것도 안 입는 경우 제외
        }
    }
}

 

의상 개수 n, 종류의 개수 k를 각각 입력받아 반복문을 돌린다.

각 의상을 입력하기 전에 cloth라는 맵을 만들어준다.

그리고 sc.next()로 의상은 스킵한 후, 종류를 next로 받아 키로 사용한다.

맵의 containsKey(키값) 를 이용해 키가 있으면 true, 없으면 false 불리언 값이므로 

1. 만약 키가 이미 있으면 get(키 값)으로 value를 가져와서 + 1한 값을 저장한다.

2. 만약 키가 없다면 해당 종류의 의상을 안입는 경우까지 2를 기본으로 입력한다.

마지막으로 values()를 이용해 int배열에서 밸류 값들을 꺼내와서 곱한다. 그다음 처음 공식대로 1을 빼주어서 정답을 구할 수 있다.

 

그리고 위 코드를 더 단축할 수도 있는데, 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            int k = sc.nextInt();
            Map<String, Integer> cloth = new HashMap<>();
            for (int j = 0; j < k; j++) {
                sc.next();
                String next = sc.next(); // 종류
                cloth.put(next, cloth.getOrDefault(next, 1) + 1);
            }
            int result = 1;
            for (int value : cloth.values()) {
                result *= value; // 경우의 수를 곱해줌
            }
            System.out.println(result - 1); // 아무것도 안 입는 경우 제외
        }
    }
}

맵의 getOrDefault를 이용하는 방법이다 (키 값, 기본 값)을 각각 입력해서

키값이 있으면 get(키)로 값을 가져와서 + 1하는 것이고, 키가 없다면 1을 가져오므로 2라는 값이 최초로 들어가게 된다.

 

마지막으로 해시맵 관련 자주쓰는 메서드 정리

메서드	설명	사용예제
put(key, value)	맵에 키와 값을 추가하거나, 키가 이미 존재하면 값을 덮어씀.	map.put("key", 2);
get(key)	키에 해당하는 값을 반환. 키가 없으면 null 반환.	map.get("key");
getOrDefault(key, defaultValue)	키에 해당하는 값을 반환하고, 키가 없으면 기본값을 반환.	map.getOrDefault("key", 1);
containsKey(key)	해당 키가 존재하면 true, 존재하지 않으면 false 반환.	map.containsKey("key");
containsValue(value)	해당 값이 존재하면 true, 존재하지 않으면 false 반환.	map.containsValue(2);
remove(key)	해당 키와 연결된 값을 제거.	map.remove("key");
size()	맵에 저장된 키-값 쌍의 개수를 반환.	map.size();
isEmpty()	맵이 비어있으면 true, 비어있지 않으면 false 반환.	map.isEmpty();
keySet()	맵의 모든 키를 Set 형태로 반환.	Set<String> keys = map.keySet();
values()	맵의 모든 값을 Collection 형태로 반환.	Collection<Integer> values = map.values();