백준 - 9375번, 패션왕 신해빈

[Silver III] 패션왕 신해빈 - 9375

문제 링크

1. 문제 설명

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

1.1 입력

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

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

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

1.2 출력

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

2. 풀이

2.1 요구사항 정리

1. 사람이 옷을 입을 때 그 날의 착장에 초점을 두고, 다음 날에는 착장에 적어도 하나의 옷 종류는 바뀌어야 한다.
2. 옷의 정보가 주어질 때, 의상의 이름과 종류가 차례로 나오는데 나오는 종류는 적어도 하나를 입어야 한다.
3. 위와 같은 논리로 매일 착장을 바꿔가며 옷을 입는다면 주어지는 옷들로 만들 수 있는 조합의 개수를 출력하라.

2.2 풀이 논리

1. 옷의 종류에 따라 옷을 골라야 하기 때문에 옷의 종류를 Key 값으로 갖고, 이름의 개수를 Value 값으로 갖는 맵으로 경우를 저장한다.
2. 아래 예제에서 순서대로 조합의 개수를 연산할 때, 이전 연산의 결과에 (새로운 옷의 종류의 개수)를 곱한 것을 더하고 (새로운 옷의 종류의 개수)를 더하면 조합의 수가 나오는 규칙성을 찾을 수 있다.

예제를 살펴보자

1. (hat), (turban), (hat, sunglasses), (turban, sunglasses), (sunglasses) → 5
2. (mask), (sunglasses), (makeup) → 3

3. “1번 예제의 eyewear에 mask를 추가”

   (hat), (turban), (sunglasses), (mask), (hat, sunglasses), (hat, mask), (turban, sunglasses), (turban, maks) → 8

4. “3번 예제의 eyewear에 makeup을 추가”

   (hat), (turban), (sunglasses), (mask), (makeup), (hat, sunglasses), (hat, mask), (hat, makeup), (turban, sunglasses), (turban, maks), (turban, makeup) → 11

2.3 코드

import java.io.*;
import java.util.*;

/*
# 요구사항 정리 #


# 풀이 논리 #

*/

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        Map<String, Integer> map = new HashMap();
        int T = Integer.parseInt(br.readLine()); // 테스트 케이스 개수
        for (int i = 0; i < T; i++) { // 모든 테스트 케이스를 탐색
            map.clear(); // 각 케이스마다 새로운 리스트로 착장의 경우를 세기 위해 clear
            int clothCnt = Integer.parseInt(br.readLine()); // 가진 의상의 수
            int nUnion = 0; // 총 조합의 개수
            for (int j = 0; j < clothCnt; j++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                String clothName = st.nextToken();
                String clothType = st.nextToken();
                // 맵에 옷 정보 저장하는 로직
                map.put(clothType, map.getOrDefault(clothType, 0) + 1);
            }
            for (Integer value : map.values()) {
                nUnion += value + nUnion * value;
            }
            sb.append(nUnion).append(" ");
        }
        System.out.print(sb);
    }
}