[백준_자료구조]9375_패션왕 신해빈

자료구조 문제는 무엇이 있을까 도전해보았던 문제.

잘 보면 key : value 구조라는걸 알 수 있다.

HashMap과 ArrayList를 이용하면 쉽게 풀 수 있는 문제라고 생각한다.

Java의 HashMap은 Map을 상속받는 클래스로 Key : Value 구조를 가진다.

사용법은 다음과 같다.

HashMap<String,String> map1               = new HashMap<>();
HashMap<Integer, String> map2             = new HashMap<>();
HashMap<String, ArrayList<String>> map3   = new HashMap<>();
HashMap<String, Friends> map4             = new HashMap<>();

HashMap<Type of Key, Value of Key> 라고 생각하면 된다.

그렇다면 HashMap의 장점은 무엇일까?

바로 "Key를 이용해 값을 꺼내올 수 있고, 원하는 Key에 값을 넣을 수 있다는 것" 이다.

우리가 배열이나, List 를 사용하게 되면 인덱스를 이용해 해당 위치에 값을 넣는다.

하지만 현실에서는 무언가 분류할 때, 숫자를 이용해 분류하는 것 보다 문자를 이용해 분류하곤 한다.

예를 들어, 우리가 옷가게의 주인이 되었다고 생각해보자.

그렇다면 우리는 판매할 옷을 옷의 종류별로 분류할 것이다.

하의 : 청바지, 양복바지, 반바지 ....

상의 : 티셔츠, 와이셔츠, V넥 ....

모자 : 비니, 털모자 ....

HashMap을 사용하면 위와 같은 분류가 가능하다.

배열을 사용했다면 0번, 1번, 2번과 같이 분류한 사람만 이해할 수 있는 방법이 되었을 것이다.

즉, HashMap의 장점은 좀 더 현실세계에 맞게 무언가 저장할 수 있다는점이 장점이라고 생각한다.

(사실 HashMap은 put 메서드를 사용하여 값을 넣을 때, key 값은 내부적으로 해쉬값으로 변경된 후, 해쉬 값에 대한 인덱스를 얻어

그 장소에 값을 저장하는 방식이다.)

ArrayList는 우리가 흔히 사용하는 배열과 매우 흡사하다.

하지만 크기가 동적으로 할당된다는 것이 장점이라고 할 수 있다.

ArrayList와 HashMap에 대해서는 나중에 좀 더 자세히 정리하는 시간을 가지도록 하겠다.

무튼 HashMap과 ArrayList를 이용하여 푼 코드를 보도록 하자.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.StringTokenizer;
 
public class Al9375 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder build = new StringBuilder();
        
        int testCase = Integer.parseInt(br.readLine());
        StringTokenizer token;
        for (int i = 0; i < testCase; i++) {
            HashMap<String, ArrayList<String> > map = new HashMap<>();
            int cnt = Integer.parseInt(br.readLine());
            for (int j = 0; j < cnt; j++) {
                token = new StringTokenizer(br.readLine());
                String item = token.nextToken();
                String key  = token.nextToken();
                if(map.containsKey(key)) {
                    map.get(key).add(item);
                }else {
                    map.put(key, new ArrayList<>());
                    map.get(key).add(item);
                }                
            }
            int ans = count(map);
            build.append(ans + "\n");
        }
        System.out.println(build.toString());
    }
    
    public static int count(HashMap<String,ArrayList<String>> map) {
        ArrayList<String> keys = new ArrayList<>();
        int ans = 1;
        for(String str : map.keySet()) {
            keys.add(str);
        }
        if(map.size() == 1) {
            return map.get(keys.get(0)).size();
        }else {
            for (int i = 0; i < map.size(); i++) {
                ans *= (map.get(keys.get(i)).size() + 1);
            }
            return ans -1;
        }
    }
}
 

위에 옷가게를 생각하며 문제를 풀면 쉽게 풀 수 있다.

또한 옷을 다 벗은 경우는 제외하기 때문에 -1을 해주는것을 잊지 마시길.