[백준] 9375번 : 패션왕 신해빈

글 작성자: ST_

www.acmicpc.net/problem/9375

9375번: 패션왕 신해빈

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

www.acmicpc.net

문제

이 번 문제도 조합과 관련된 문제다. 그리 어렵지 않으니 쉽게 풀 수 있을 것이다.

알고리즘 [접근 방법]

밑에 있는 힌트란을 읽어보았다면 문제는 금방 이해가 갈 것이다.

의상 이름과 의상 종류가 주어지고, 한 번 입었던 '조합'은 다시 입지 않는다는 것과, 옷의 종류가 중복되게 입을 수 없다는 것이 중요한 포인트다.

즉, 위의 예제로 예시로 들면 이렇다.

[headgear]

hat

turban

[eyewear]

sunglasses

이렇게 두 종류의 옷과 세 개의 옷의 이름이 주어져있다. 그리고 알몸이 되지 않으면서 조합을 짜보자면 이렇다.

한 개만 입을 경우 : {hat}, {turban}, {sunglasses}

두 개씩 조합하여 입을 경우 : {hat, sunglasses}, {turban, sunglasses}

불가능한 조합 1 (옷의 종류가 겹치는 경우)

{hat, turban}, {hat, turban, sunglasses}

자 그럼 한 번 공식으로 만들어보자.

일단 같은 종류의 옷을 중복해서 입을 수 없기 때문에 '종류별로' 구분을 한 뒤 각각의 경우의 수를 구하는 것이다.

[headgear] : hat, turban

[eyewear] : sunglasses

이제 각각 분류된 옷에 대하여 경우의 수를 구해야 한다. 앞서 문제 조건에서 같은 종류의 의상은 하나만 입을 수 있다고 했으니, 한 종류에 있는 옷의 개수에서 1개를 선택하는 경우를 구해야 한다.

그럼 headgear에서 경우의 수는 총 몇 가지 인가? 2인가? 아니다. 총 3가지다.

옷을 입을 경우만 생각한다면 물론 2가지이겠으나, 우리가 고려애햐 할 것은 '옷을 안 입는 경우'도 있다는 것이다.

eyewear 도 마찬가지다. 안 입는 경우 까지 고려하면 총 경우의 수는 2가지다.

즉, 다시 표현하자면 이렇다. (안입는 경우를 NULL 로 표기함)

[headgear] : hat, turban, NULL

[eyewear] : sunglasses, NULL

그러면 headgear 에 대해서는 ₃C₁ 을 구하면 되고, eyewear 에 대해서는 ₂C₁ 을 구하면 된다.

₃C₁ = 3

₂C₁ = 2

이 둘을 곱하면 종류별로 조합하는 공식이 나온다.

₃C₁ × ₂C₁ = 3 × 2 = 6

그리고 마지막으로 중요한 점이 있다.

'알몸이 아닌 상태로 며칠까지 가능한지'를 물어보는 것이기 때문에 알몸일 경우는 위에서 headgear에서 NULL이 선택되고, eyewear에서 NULL이 선택된, 즉 두 종류 모두 안 입는 경우가 있기 때문에 마지막에 1을 빼주어야 한다.

즉, 아래와 같이 계산하면 된다.

₃C₁ × ₂C₁ - 1

= 3 × 2 - 1

= 5

이를 일반화한다면 이렇다.

옷의 종류별로 개수를 세어준 다음 각 종류별 경우의 수를 구하여 곱한다음 마지막에 -1을 해주는 것이다. 그리고 각 종류별로는 결국 1개 밖에 선택 할 수 없으니 '_nC₁ = 옷의 개수'이다. 즉 각 종류별 옷의 개수만 알면 끝이라는 것.

수식으로 표현하자면 이렇다.

종류 k에 대한 옷의 개수가 N개일 때,

경우의 수 = (N₁ + 1) × (N₂ + 1) × ⋯ × (N_k-1 + 1) × (N_k + 1) - 1

(앞서 말했듯이 각 종류별 입지 않는 경우를 고려하여 각 종류별 개수 + 1 을 해주어야 하며 최종 값에 알몸인 상태(모든 종류를 입지 않은 상태)를 제외해야 하므로 -1 을 빼준다.)

이렇게 짤 수 있다.

그럼 어떻게 종류별로 개수를 셀 것인지를 고민하면 되는데, 별로 고민할 것 없이 자바에서는 HashMap 이라는 클래스가 있기 때문에 이를 이용해주면 된다.

즉, 간략하게 알고리즘을 짜보자면 이렇다.

Map<String, Integer> hm = new HashMap<>();	// <종류, 개수>

int N = input();	// 입력받는 총 옷의 개수

while (N-- > 0) {
				
	inputString();	// 옷 이름은 필요 없음
	String kind = inputString();	// 옷 종류


	/**
	 * 해당 종류의 옷이 해시맵에 있을경우
	 * 해시맵에 저장되어있던 해당 종류의 개수를 +1 증가시킨다.
	 *
	 * 해당 종류의 옷이 해시맵에 없을 경우
	 * 해당 종류와 개수 1을 넣는다.
	 */
     
	if (hm.containsKey(kind)) {
		hm.put(kind, hm.get(kind) + 1);
	} 
	else {
		hm.put(kind, 1);
	}
}

int result = 1;	

/**
 * 안 입는 경우를 고려하여 각 종류별 옷의 개수에 +1 해준 값을
 * 곱해주어야 한다.
 */
for (int val : hm.values()) {
	result *= (val + 1);
}

print(result - 1);	// 알몸인 상태를 제외해주어야 하므로 최종값에 -1이 정답.

위와 같은 알고리즘을 사용하면 된다. 다만 위 과정을 첫 째줄에 입력받는 테스트 케이스만큼 반복만 해주면 끝.

3가지 방법을 사용하여 풀이한다.

알고리즘은 위의 것을 그대로 쓸 것이다. 입력 방법에 따른 비교를 해보고, 마지막으로 HashMap을 안쓰고 풀이 하는 방법을 보여주고자 한다. (정확히는 HashMap의 구조를 이용하여 풀이하는 방법이다.)

1 . Scanner + HashMap

2. BufferedReader + HashMap

3. BufferedReader + Custom HashMap

풀이

- 방법 1 : [Scanner + HashMap]

import java.util.Scanner;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);

		int T = in.nextInt();	// 테스트 케이스 

		while (T -- > 0) {
			
			HashMap<String, Integer> hm = new HashMap<>();	// <종류, 개수>
			
			int N = in.nextInt();	// 입력받는 옷의 개수
			
			while (N-- > 0) {
				
				in.next();	// 옷 이름은 필요 없음 
				
				String kind = in.next();	// 옷 종류 

				/**
				 * 해당 종류의 옷이 해시맵에 있을경우
				 * 해시맵에 저장되어있던 해당 종류의 개수를 +1 증가시킨다.
				 *
				 * 해당 종류의 옷이 해시맵에 없을 경우
				 * 해당 종류와 개수 1을 넣는다.
				 */
				
				if (hm.containsKey(kind)) {
					hm.put(kind, hm.get(kind) + 1);
				} 
				else {
					hm.put(kind, 1);
				}
			}

			int result = 1;

			/**
			 * 안 입는 경우를 고려하여 각 종류별 옷의 개수에 +1 해준 값을
			 * 곱해주어야 한다.
			 */
			for (int val : hm.values()) {
				result *= (val + 1);
			}
	
			System.out.println(result - 1);		// 알몸인 상태를 제외해주어야 하므로 최종값에 -1이 정답.

		}

	}

}

가장 기본적인 방법이라 할 수 있겠다.

- 방법 2 : [BufferedReader + HashMap]

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 또한 출력 부분에서도 좀 더 좋게 StringBuilder을 사용하도록 하겠다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
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));
		StringBuilder sb = new StringBuilder();

		int T = Integer.parseInt(br.readLine());	// 테스트 케이스 

		while (T -- > 0) {
			
			HashMap<String, Integer> hm = new HashMap<>();	// <종류, 개수>
			
			int N = Integer.parseInt(br.readLine());	// 입력받는 옷의 개수
			
			while (N-- > 0) {
				StringTokenizer st = new StringTokenizer(br.readLine(), " ");
				
				st.nextToken();	// 옷 이름은 필요 없음 
				
				String kind = st.nextToken();	// 옷 종류 

				/**
				 * 해당 종류의 옷이 해시맵에 있을경우
				 * 해시맵에 저장되어있던 해당 종류의 개수를 +1 증가시킨다.
				 *
				 * 해당 종류의 옷이 해시맵에 없을 경우
				 * 해당 종류와 개수 1을 넣는다.
				 */
				
				if (hm.containsKey(kind)) {
					hm.put(kind, hm.get(kind) + 1);
				} 
				else {
					hm.put(kind, 1);
				}
			}

			int result = 1;

			/**
			 * 안 입는 경우를 고려하여 각 종류별 옷의 개수에 +1 해준 값을
			 * 곱해주어야 한다.
			 */
			for (int val : hm.values()) {
				result *= (val + 1);
			}
			// 알몸인 상태를 제외해주어야 하므로 최종값에 -1이 정답.
			sb.append(result - 1).append('\n');

		}
		System.out.println(sb);
	}

}

크게 어려울 것은 없을 것이다. 이번 문제는 중복을 고려하지 않아도 되니 오히려 쉬웠을 수도 있다.

- 방법 3 : [BufferedReader + Custom HashMap]

HashMap 원리 자체가 HashMap<Key, Value> 형식으로, Key에 대해 hash함수를 돌려서 고유한 값을 갖도록 하고, 해당 값에 대한 데이터를 저장하는 것이다.

이를 이용하면 우리가 카운팅 정렬을 했던 것 처럼 옷 종류로 들어오는 입력값을 해시함수로 돌려서 해당 고유값을 배열에 저장해두고 쓸 수도 있다.

그럼 해시함수를 어떻게 얻냐가 문제인데, 기본적으로 자바에서는 Object.hashcode() 라는 함수가 있고, 해당 객체를 해시함수로 돌려서 고유값을 반환한다.

위 함수를 이용함과 동시에 HashMap에서는 hashcode값과 hashcode를 16비트 이전시킨 값을 XOR 연산하여 얻은 값을 key값으로 쓴다.

쉽게 말하자면 다음과 같이 쓴다는 것.

static final int hash(Object key) {
	int h;
	return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

무슨 말인지 이해하기 어렵다면 코드를 보면서 이해해보자.

참고로 배열로 쓰기 위해서는 결국 한정된 크기 내에서 저장할 수 밖에 없기 때문에 적절히 큰 소수인 10007으로 나눈 나머지를 인덱스 값으로 쓸 것이다.

그러나 알아두어야 할 것은 hashcode로 얻은 값을 mod(%) 연산을 하는 것은 매우 위험한 일이다. 왜냐하면 mod 연산을 하면 고유성을 잃어버릴 확률, 즉 겹칠 확률이 매우 높아지기 때문에 적절하게 소수이면서 큰 수로 나눠주어야 한다.

추가로 16비트를 밀어내어 XOR 연산을 할 경우 음수값이 나올 수 있다.(가장 끝 비트가 1일 때는 음수값을 의미) 그렇기 떄문에 배열에 저장하기 위해 위에서 얻은 값을 절댓값을 써야한다.

그리고 16비트를 밀어내지 않고 그냥 hashCode 함수만 써도 된다. 다만, HashMap의 내부가 어떻게 되어있는지를 보여주고싶어서 아래처럼 작성할 것이다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {
	
	public final static int MOD = 10007;
    
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int T = Integer.parseInt(br.readLine());	// 테스트 케이스 

		while (T -- > 0) {
			
			int[] table = new int[MOD];
			
			int N = Integer.parseInt(br.readLine());	// 입력받는 옷의 개수
			
			while (N-- > 0) {
				StringTokenizer st = new StringTokenizer(br.readLine(), " ");
				
				st.nextToken();	// 옷 이름은 필요 없음 
				
				table[hash(st.nextToken())]++;	// 옷 종류 
			}

			int result = 1;

			/**
			 * 안 입는 경우를 고려하여 각 종류별 옷의 개수에 +1 해준 값을
			 * 곱해주어야 한다.
			 */
			for (int val : table) {
				result *= (val + 1);
			}
			result--;		// 알몸인 상태를 제외해주어야 하므로 최종값에 -1이 정답.
			sb.append(result).append('\n');	
			table = null;
		}
		System.out.println(sb);
	}
	
	static int hash(String s) {
		return Math.abs(s.hashCode() ^ (s.hashCode() >>> 16)) % MOD;
	}

}

더 작은 수로 나눠서 통과를 하는지 테스트 해보려 했으나 대략 열댓번 틀렸다고 나와서 그냥 10007 로 나눈 나머지값으로 쓰는 것에 만족하고 있다. 혹여 다른 수로도 통과 된다면 댓글 달아주면 감사하겠다...

성능

채점 번호 : 23657434 - 방법 3 : BufferedReader + Custom HashMap

채점 번호 : 23657428 - 방법 2 : BufferedReader + HashMap

채점 번호 : 23657424 - 방법 1 : Scanner + HashMap

입력의 경우는 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다. 참고로 방법 3에서 hash메소드를 final로 변경하면 위의 96ms 보다 조금 더 빠른 결과를 낼 수 있을 것이다. (컴파일러가 코드를 정적으로 최적화 하는데 도움이 되기 때문이다.)

정리

정답비율이 50% 을 넘는 것을 보아 아마 다들 쉽게 풀었던 것 같다.

방법 3에서 좀 더 겹치지 않게 하는 방법을 찾고싶은데 틀렸습니다를 너무 많이 받아서.. 그만 포기했다만, 혹여 MOD값을 다른 값으로 하여 통과하신 분이 있다면 같이 공유하면 좋겠다..

아무튼 HashMap에서 해싱이 어떻게 이루어지는지에 대한 잡지식으로 알고가면 좋을 것 같아 한 번 보여주었다. 혹여 모르거나 어려운 부분이 있다면 댓글 달아주시면 최대한 빠르게 답변드리도록 하겠다 :)

저작자표시 비영리 변경금지

'JAVA - 백준 [BAEK JOON] > 정수론 및 조합론' 카테고리의 다른 글

[백준] 2004번 : 조합 0의 개수 - JAVA [자바] (14)	2020.11.07
[백준] 1676번 : 팩토리얼 0의 개수 - JAVA [자바] (27)	2020.11.05
[백준] 11051번 : 이항 계수 2 - JAVA [자바] (12)	2020.10.30
[백준] 11050번 : 이항 계수 1 - JAVA [자바] (17)	2020.10.27
[백준] 3036번 : 링 - JAVA [자바] (0)	2020.10.23

[백준] 9375번 : 패션왕 신해빈 - JAVA [자바]

'JAVA - 백준 [BAEK JOON] > 정수론 및 조합론' 카테고리의 다른 글

댓글

이 글 공유하기

티스토리툴바

'JAVA - 백준 [BAEK JOON] > 정수론 및 조합론' 카테고리의 다른 글

댓글

이 글 공유하기

다른 글

[백준] 2004번 : 조합 0의 개수 - JAVA [자바]

[백준] 1676번 : 팩토리얼 0의 개수 - JAVA [자바]

[백준] 11051번 : 이항 계수 2 - JAVA [자바]

[백준] 11050번 : 이항 계수 1 - JAVA [자바]

티스토리툴바