[Java 자바] 백준 알고리즘 9375번 : 패션왕 신해빈 | 반례

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

9375번: 패션왕 신해빈

 

 

이 문제에 대한 아주 훌륭한 풀이는 이분 블로그에 있고.. (정말 애용한다.. 설명이 기가막힌다.. 천재신듯..)

https://st-lab.tistory.com/164

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

 

※우선 이 포스트는 해당 문제의 풀이를 다루지 않는다.

풀이를 원하시는 분은 바로 위의 링크건 블로그를 방문하시길 강추한다. 

혹시라도 나와 같은 실수를 하신 분들이 "내 풀이는 뭐가 틀린거지?" 싶으실 것 같아서.. 공유해본다.

 

일단 나는 이 문제의 예시를 보고 풀이를 이렇게 짜보았다.

map에 <String, Integer>로 저장하고나서

1. 각 key(종류)마다의 value를 다 더해준 후에 (각각만 착용하는 경우) >> 2+1 = 3

2. 각 종류별로 하나씩 매칭해서 입는 경우 >> 2X1 = 5

답 : 1번 + 2번 = 5

[headgear] : hat, turban

[eyewear] : sunglasses

 

이렇게 짜고 

 

아래의 예시의 경우만 예외처리로 키가 1개만 있을 때는 

1. 각 key(종류)마다의 value를 다 더해준 후에 (각각만 착용하는 경우) >> 3

답 : 1번 = 3

[face] : mask, sunglasses, makeup

 

이렇게 짰었다.

 

틀린 코드지만, 이해를 돕기위해 내가 짠 코드를 첨부한다.

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        for(int i=0;i<t;i++) {
            int answer = 0;
            int mul = 1;
            HashMap<String, Integer> map = new HashMap<>();
            int n = Integer.parseInt(br.readLine());
            for(int j=0;j<n;j++){
                st = new StringTokenizer(br.readLine());
                String s1 = st.nextToken();
                String s2 = st.nextToken();
                map.put(s2, map.getOrDefault(s2,0)+1);
            }
            int cnt = 0; // key가 한개만 있는 경우를 세려고
            for(String s : map.keySet()){
                int tmp = map.get(s);
                mul *= tmp;
                answer += tmp;
                cnt++;
            }
            if(cnt > 1)
                answer += mul;
            sb.append(answer).append("\n");
        }
        System.out.println(sb);
    }
}

 

틀렸길래,, 뭐가 문제지,, 생각해봤더니

종류가 3가지 이상인 경우는 포함하지 못하더라,,,

 

내 알고리즘에 대한 반례를 들면, 이러한 예시가 있다고 하면 

[headgear] : hat, turban

[eyewear] : sunglasses

[face] : mask, makeup

 

내가 짠 알고리즘대로라면 

1. 각 key(종류)마다의 value를 다 더해준 후에 (각각만 착용하는 경우) >> 2+1+2 = 5

2. 각 종류별로 하나씩 매칭해서 입는 경우 >> 2X1X2 = 4

답 : 1번 + 2번 = 9

이렇게 나오는데 실제로 경우의 수는

(hat) (turban) (sunglasses) (mask) (makeup)

(hat, sunglasses) (hat, mask) (hat, makeup) (turban, sunglasses) (turban, mask) (turban, makeup)

(sunglasses, mask) (sunglasses, makeup) 

(hat, sunglasses, mask) (hat, sunglasses, makeup) (turban, sunglasses, mask) (turban, sunglasses, makeup) 

 

가운데 빨간색처럼 세 종류 중에 하나만 착용을 안하는 경우도 있기 때문에..

내가 짠 알고리즘으로는 이 경우를 생각해주지 못한다.. 바보였당,,

 

<직접 프로그램에 넣어볼 수 있는 반례>

1
5
a 1
b 1
c 2
d 3
e 3

답 : 17

 

저같은 실수를 하신 분들에게 도움이 되었길 바라며,,,