[Python] BOJ/백준 9375번 패션왕 신해빈

[문제]

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

9375번: 패션왕 신해빈

 

[풀이]

if kinds in closet.keys():
    closet[kinds].append(costume)
else:
    closet[kinds] = []
    closet[kinds].append(costume)

의상 종류가 closet 딕셔너리에 있다면 의상을 종류에 맞게 value 리스트에 추가해주고, 없을 경우 종류에 리스트를 초기화한 후 해당 리스트에 의상을 추가해준다.

 

 

for key in closet:
    res *= len(closet[key]) + 1
    print(res - 1)

해당 종류의 의상을 안입을 경우도 있기 때문에 의상 종류의 개수 + 1을 해 곱한다. 해빈이가 알몸이면 안되기 때문에 곱한 결과에서 알몸인 경우 1을 뺀 수가 답이 된다.

 

[코드]

import sys

if __name__ == '__main__':
    for _ in range(int(sys.stdin.readline())):
        closet = {}
        n = int(sys.stdin.readline())
        for __ in range(n):
            costume, kinds = map(str, sys.stdin.readline().split())
            # 의상의 종류 저장
            if kinds in closet.keys():
                closet[kinds].append(costume)
            else:
                closet[kinds] = []
                closet[kinds].append(costume)

        res = 1
        for key in closet:
            res *= len(closet[key]) + 1
        print(res - 1)

같은 이름의 의상이 중복으로 들어오지 않기 때문에 굳이 의상의 이름을 저장할 필요가 없겠다는 생각을 하게 됨

-> 각 카테고리 별 의상 개수만 알면 되는 것

 

- 리팩토링 코드

import sys

if __name__ == '__main__':
    for _ in range(int(sys.stdin.readline())):
        closet = {}
        n = int(sys.stdin.readline())
        for __ in range(n):
            costume, kinds = map(str, sys.stdin.readline().split())
            # 의상의 종류 저장 X, 개수만 저장
            if kinds in closet.keys():
                closet[kinds] += 1
            else:
                closet[kinds] = 1

        res = 1
        for key in closet:
            res *= closet[key] + 1
        print(res - 1)

작은 차이!

---

+

나는 조합을 이용해 문제를 풀었지만 문제의 힌트가 '해시를 사용한 집합과 맵' 이라 해시를 사용한 경우의 코드가 궁금해졌다. 검색해보니 다들 조합을 이용해 문제를 풀어서 자바를 이용한 해시 풀이밖에 구하지 못했다.

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

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int testCase = sc.nextInt();
        for (int t = 0; t < testCase; t++) {
            HashMap<String, Integer> map = new HashMap<>();
            int n = sc.nextInt();
            for (int i = 0; i < n; i++) {
                String name = sc.next();
                String type = sc.next();
                map.put(type, map.getOrDefault(type, 0) + 1);
            }
            int answer = 1;
            for (String key : map.keySet()){
                answer *= (map.get(key) + 1);
            }
            System.out.println(answer-1);
        }
    }
}

 

[알고리즘] 백준 9375 패션왕 신해빈 -해시(hash)- 자바