[백준] 9375 패션왕 신해빈 - HashMap(해시맵) + 시간초과(경우의 수에 대한 이해) JAVA

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

9375번: 패션왕 신해빈

코드설명

HashMap + 경우의 수에 대한 이해 문제입니다.

 

처음에 풀었을떄는 각 경우에 대한 조합을 만들었습니다.

즉, 1개로 이루어진 조합, 2개로 이루어진 조합, 3개로 이루어진 조합 ... 을 만든뒤에

각 경우에서 만들어질 수 있는 경우의 수를 모두 더했습니다.

 

하지만 시간초과가 발생합니다. 

먼저 왜 시간초과가 발생하는지 알아봅니다.

테스트케이스 T는 100입니다.

해빈이가 가진 의상의 수는 최대 30개입니다. 

 

현재 시간복잡도는,

입력처리에는 O(TN).

조합계산에는 O(2^N) 입니다.(선택할지 말지 2가지 경우의 수를 N번 반복합니다.)

N = 30 이므로 2^30(1073741824) 이므로, 문제에서 주어진 1초 안에는 미세한 차이로 불가합니다.

 

더 좋은 방식이 있습니다.

문제에서는 "옷을 입지 않는 경우"를 구해야만 합니다.

그렇다면, 옷을 입지 않는 경우 1개를 각 옷의 종류에 한개씩 추가합니다.

그리고 마지막에 옷을 입지 않는 경우가 모든 옷의 종류에서 선택되는 경우인 1 가지를 뺴주면됩니다.

 

이렇게 문제를 풀 수 있는 방법을 생각해야한다는점에서 좋은 문제인 것 같습니다.

코드

package algorhythm;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.StringTokenizer;
 
public class Main {
	public static int N, C, T;
	public static HashMap<String, Integer> hashmap = new HashMap<>();
	public static int answer = 0;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		T = Integer.parseInt(st.nextToken());
		
		while(T-- > 0) {
			hashmap = new HashMap<>();
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			for(int i=0;i<N;i++) {
				st = new StringTokenizer(br.readLine());
				String a = st.nextToken();
				String b = st.nextToken();
				
				hashmap.put(b, hashmap.getOrDefault(b, 0) + 1);
			}
			
			answer = 1;
			//만약 들어온 옷의 종류가 1개라면, 각각의 개수만 더해집니다.
			for(Entry<String, Integer> entrySet : hashmap.entrySet()) {
				answer *= (entrySet.getValue() + 1);
			}
			answer -= 1;
			System.out.println(answer);
			
		}
	}
}

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
 
public class Main {
    public static int N, T, M; 
    public static int answer = 0;
    public static int[] cache;
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
 
		T = Integer.parseInt(st.nextToken());
		cache = new int[11];
		Arrays.fill(cache, -1);
		while(T-- > 0) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			HashMap<String, Integer> hashmap = new HashMap<>();
			
			for(int i=0;i<N;i++) {
				st = new StringTokenizer(br.readLine());
				String clothName = st.nextToken();
				String clothKind = st.nextToken();
				hashmap.put(clothKind, hashmap.getOrDefault(clothKind, 0) + 1);
			}
			
			answer = 1;
			for(Map.Entry<String, Integer> entrySet : hashmap.entrySet()){
				answer = answer * (entrySet.getValue() + 1);
			}
			
			answer -= 1;
			System.out.println(answer);
		}
	}
    
}

 

모든 조합마다의 각 시간을 모두 연산합니다. 시간복잡도(2^N)

그렇기에, 시간초과가 나는 코드입니다.

package algorhythm;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.StringTokenizer;
 
public class Main {
	public static int N, C, T;
	public static HashMap<String, Integer> hashmap = new HashMap<>();
	public static StringBuilder sb = new StringBuilder();
	public static int answer = 0;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		T = Integer.parseInt(st.nextToken());
		
		while(T-- > 0) {
			hashmap = new HashMap<>();
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			for(int i=0;i<N;i++) {
				st = new StringTokenizer(br.readLine());
				String a = st.nextToken();
				String b = st.nextToken();
				
				hashmap.put(b, hashmap.getOrDefault(b, 0) + 1);
			}
			
			answer = 0;
			int size = hashmap.keySet().size();
			int[] value = new int[size];
			int index = 0;
			//만약 들어온 옷의 종류가 1개라면, 각각의 개수만 더해집니다.
			for(Entry<String, Integer> entrySet : hashmap.entrySet()) {
				value[index++] = entrySet.getValue();
			}
			
			for(int i=1; i<=size;i++) {
				//combination (1), combination(2) .. 가 실행됨. 
				//그러면 1 일때 3. 2일때 2개. 로 5가 나와야함.
				combination(0, 0, i, value, new int[i]);
			}
			sb.append(answer);
		}
		
		System.out.println(sb.toString());
	}
	
	public static void combination(int level, int idx, int maxSize, int[] value, int[] selected) {
		if(level == maxSize) {
			//원하는 숫자만큼 정해졌다면, 해당 내에서 나올 수 있는 개수를 구합니다.
			int temp = 1;
			for(int i=0;i<selected.length;i++) {
				temp *= value[selected[i]];
			}
			answer += temp;
			
			return ;
		}
		
		for(int i=idx;i<value.length;i++) {
			selected[level] = i;
			combination(level + 1, i + 1, maxSize, value, selected);
			selected[level] = -1;
		}
		
	}
}