[백준] 9375번_패션왕 신해빈(Java)

문제 풀이

백준의 9375번 문제입니다. 문제 출처

(1) 문제 파악

(2) 문제 풀이 방법 생각하기

이 문제에서는 옷의 종류마다 몇 개의 옷이 있는지 확인하는 것이 중요합니다. 같은 이름을 가진 옷은 없다고 했으니 중복 관련 처리는 신경쓰지 않아도 되겠네요!

예제를 통해 이해를 해보자면..

옷의 종류는 headgear, eyewear 두 가지가 있고, 각 종류마다 구성품은 다음과 같습니다. {headgear: [hat, turban]}, {eyewear: [sunglasses]}

각각의 옷 종류는 입지 않는 선택지도 포함되어 있기 때문에 종류마다 +1을 해서 곱해주어야 합니다.

(2+1) * (1+1) 을 하면 아래와 같은 6가지 경우가 나오게 됩니다.

그러나 문제에서는 모두 안 입는 경우는 없기 때문에 마지막 결과에서 -1을 해주면 됩니다!!

(3) 시간 복잡도 확인

시간 제한은 1초 입니다. 즉, 대략 1억번 연산 안에 문제를 해결해야 합니다.

\[1 <= T <= 100\] \[0 <= N <= 30\]

N의 최대값이 30이므로 옷의 종류는 최대 30개입니다. O(T * 2 * N) 이므로 문제 해결이 가능합니다!

• map에 값 초기화해서 넣는 연산 최대 N번
• 값을 곱하는 연산 최대 N번

(4) 구현

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
       
        int T = Integer.parseInt(br.readLine());
        StringTokenizer st;

        for(int i=0; i<T; i++) {
            Map<String, Integer> clothes = new HashMap<>();
            int N = Integer.parseInt(br.readLine());

            for(int j=0; j<N; j++) {
                st = new StringTokenizer(br.readLine());
                st.nextToken();
                String key = st.nextToken();

                clothes.put(key, clothes.getOrDefault(key, 0)+1);
            }

            int count = 1;
            for(Map.Entry<String, Integer> eMap : clothes.entrySet()) {   
                count *= (eMap.getValue()+1);
            }

            bw.append(count-1 + "\n");
        }
        
        bw.flush();
        br.close();
        bw.close();
    }
}