문제

BOJ 9375, 패션왕 신해빈

핵심

• 테스트 크기는 100이며, 의상의 수 30, 의상의 종류는 1이상 20이하의 알파벳 소문자로 이루어져 있다. 의상의 종류가 의상의 수를 넘을 수 없으므로 입력 범위는 한정적이고, 구현에 초점을 맞춘다.
• 해빈이가 입을 수 있는 옷들의 조합을 구해야 한다. 의상의 종류가 다르면 겹쳐 입을 수 있으므로 이는 해빈이가 매번 옷을 입거나, 안 입는 걸 선택할 수 있는 조합 문제이다.
• 의상의 종류를 파악해야 하고, 해당 의상이 몇 개 있는지도 알아야 하기에 해시 자료구조인 map을 사용한다. 알몸이 아닌 상태로 입을 수 있는 경우의 수를 구하라 했으므로 전체 경우의 수에서 알몸인 경우(모두 선택하지 않은 경우)를 차감하여 구할 수 있다.

개선

• 처음에 unordermap에 key, value를 저장할 때 기본값이 0이 있는지 모르고 find로 검색 후 없으면 0, 있다면 기존 값 + 1로 저장했다. c++에선 해당하는 키에 대한 값은 기본생성자를 사용하여 초기화하므로 int의 경우 0으로 초기화되어 있다.

코드

시간복잡도

• $O(T\times N)$

C++

#include <iostream>
#include <unordered_map>
using namespace std;

int main(void) { 
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		unordered_map<string, int> m;
		for (int i = 0; i < n; ++i) {
			string cName, cType;
			cin >> cName >> cType;
			m[cType]++;
		}
		int ans = 1;
		for (auto e : m)
			ans *= e.second + 1;
		cout << ans - 1 << '\n';
	}	
}

Java

import java.io.*;
import java.util.HashMap;
import java.util.StringTokenizer;

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());
        for (int i = 0; i < t; i++) {
            HashMap<String, Integer> map = new HashMap<>();
            int n = Integer.parseInt(br.readLine());
            for (int j = 0; j < n; j++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                st.nextToken();
                String type = st.nextToken();
                map.put(type, map.getOrDefault(type, 0) + 1);
            }
            int ans = 1;
            for (var c : map.values())
                ans *= c + 1;
            bw.write(ans - 1 + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}