[Baekjoon] 9375 패션왕 신해빈 - JAVA

문제

해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경대신 렌즈를 착용하거나 해야한다. 해빈이가 가진 의상들이 주어졌을때 과연 해빈이는 알몸이 아닌 상태로 며칠동안 밖에 돌아다닐 수 있을까?

 

---

입력

첫째 줄에 테스트 케이스가 주어진다. 테스트 케이스는 최대 100이다.

• 각 테스트 케이스의 첫째 줄에는 해빈이가 가진 의상의 수 n(0 ≤ n ≤ 30)이 주어진다.
• 다음 n개에는 해빈이가 가진 의상의 이름과 의상의 종류가 공백으로 구분되어 주어진다. 같은 종류의 의상은 하나만 입을 수 있다.

모든 문자열은 1이상 20이하의 알파벳 소문자로 이루어져있으며 같은 이름을 가진 의상은 존재하지 않는다.

---

출력

각 테스트 케이스에 대해 해빈이가 알몸이 아닌 상태로 의상을 입을 수 있는 경우를 출력하시오.

---

예제 입력 1 

2
3
hat headgear
sunglasses eyewear
turban headgear
3
mask face
sunglasses face
makeup face

예제 출력 1 

5
3

---

힌트

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

---

📝 제출 답안

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            int count = Integer.parseInt(br.readLine());
            sb.append(combinationCount(count)).append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
    }

    public static int combinationCount(int count) throws IOException {
        HashMap<String, Integer> map = new HashMap<>();
        for (int i = 0; i < count; i++) {
            st = new StringTokenizer(br.readLine());
            String name = st.nextToken();
            String form = st.nextToken();
            map.put(form, map.getOrDefault(form, 0) + 1);
        }

        int combination = 1;
        for (int duplicate : map.values()) {
            combination *= (duplicate + 1);
        }
        return combination - 1;
    }
}

 

입출력

BufferedReader와 BufferedWrite로 입출력의 효율성을 높이고자 하였다.

각 테스트 케이스에 대한 계산 결과는 StringBuilder에 저장해 한 번에 출력하였다.

 

combination 메서드

우선 주어진 문제에서 의상 이름과 의상 종류를 입력받는데 의상 종류만 겹치지 않도록 조합을 확인하면 되는 것이므로 의상 이름을 따로 저장할 필요는 없다고 생각했다. 그래서 해시맵으로 의상의 종류 form과 의상 종류가 중복되는 횟수를 저장하도록 하였다.

map에 의상 종류 form은 key값으로, 중복 횟수는 value값으로 저장한다.

getOrDefault() 메서드를 사용해주었다.

form 값이 이미 존재하면 해당 값에 1을 더하고, 존재하지 않으면 디폴트 값으로 0을 저장하도록 한다.

map.put(form, map.getOrDefault(form,0) + 1);

 

각 form에서 아이템을 선택하는 경우의 수는 (duplicate + 1)이다.

duplicate 는 해당 form 값의 중복 개수이고,

선택하지 않은 경우를 포함하기 위해 1을 더해준다.

combination 변수에 모든 form의 선택 가능 조합을 곱하여 전체 조합의 수를 계산한다.

마지막에 최종 값을 반환할 때 combination에는 공집합이 포함되어 있으므로 1을 빼주고 반환한다.

int combination = 1;
for (int duplicate : map.values()) {
    combination *= (duplicate + 1);
}
return combination - 1;

 

 

제출 현황