99클럽 코테 스터디 6일차 TIL + 오늘의 학습 키워드 : 경우의수

오늘의 회고

- 오늘의 문제

- 문제가 참 어렵다...

  경우의 수 문제는 규칙을 잘 찾으면 참 쉬운데

  규칙을 찾을 때까지가 쉽지 않다...

- 솔직히 좀만 침착하게

  경우의 수를 구해보며 규칙을 찾았다면

  이렇게 까지 걸릴 문제는 아니었을 것이다.

  자꾸 머릿속으로 생각하고 이상한 짓을 해서 그런거 같다.

 

- 정답

import java.util.*;
class Solution {
    public int solution(String[][] clothes) {
        HashMap<String, Integer> map = new HashMap<>();
        for(int i = 0; i < clothes.length; i++){
            if(map.containsKey(clothes[i][1])){
                map.put(clothes[i][1], map.get(clothes[i][1]) + 1);
                continue;
            }
            map.put(clothes[i][1], 2);
            // 2인 이유는 하나의 의상의 종류 당 안입는 경우의 수 1을 추가해야 하기 때문
        }
        int multiple = 1;
        for(int i : map.values()){
            multiple = multiple * i;
        }
        
        return multiple - 1;
    }
}

 

- 처음 생각했던 방법 -

import java.util.*;
class Solution {
    public int solution(String[][] clothes) {        
        HashSet<String> hashSet = new HashSet<>();
        
        for(int i = 0; i < clothes.length; i++){
            hashSet.add(clothes[i][1]);
        } // 의상의 종류 총 갯수를 알기 위한 set
        HashMap<String, Integer> hashMap = new HashMap<>();
        for(String s : hashSet){
            hashMap.put(s, 0);
        } // 각 의상의 종류 별 의상 갯수를 위한 hashMap
        for(int i = 0; i < clothes.length; i++){
            hashMap.put(clothes[i][1], hashMap.get(clothes[i][1]) + 1);
        } //찾을 때마다 +1
        int count = 0;
        ArrayList<Integer> list = new ArrayList<>(hashMap.values());
        for(int i: list){
            count = count + i;
        } // 하나씩만 입는 경우의 수
        int factorial = 1;
        if(hashSet.size() > 1){
            for(int i = 0; i < list.size(); i++){
                factorial = factorial * list.get(i);
            }
            count = count + factorial;
        } // 3 * 2 * 2 처럼 생각해서 이렇게 작성
        
        int answer = count;
        return answer;
    }
}

- 총 경우의 수를 구할 때, 나는 겹치지 않게 입는 경우의 수를 위해

  그냥 의상 종류 별 갯수를 다 곱해주었다.

  이렇게 하니 테스트 통과를 했다.

  하지만, 제출하니 거의 다 틀려서 다른 방법을 생각해야만 했다.

  그러던중, HashMap 만으로도 갯수를 지정해줄 수 있다고 생각이 들어

  코드가 좀 줄었다.

  그래도 계속 틀려서 처음으로 돌아갔다.

  새로운 테스트 케이스를 추가해서 실행하니 틀린 것이었다.

  내가 처음에 생각한 방법이 전혀 틀린 것이었다.

  그래서 규칙을 찾자 다시 다짐하였고,

  써보았다.

3*2 - 1 // 테스트 케이스 1
4*1 - 1 // 테스트 케이스 2

3*3*2 - 1 // 이건 내가 생각한 테스트 케이스
5 + 10 + 2 = 17

- 처음엔 입는/안입는 경우를 생각해서

  2의 n(의상의 종류별 의상의개수) 제곱으로 접근하였다.

  그랬더니 값이 너무 커져서 이상해졌다.

  어떻게 줄일까 생각하다가

  n이 2라면, [ 1번을 입는/2번을 입는/둘다 안입는 ]

  총 3개, 그니깐 (n + 1)로 계산을 해보았다.

  뭐 이렇게 얘기했지만, 억지로 끼워 맞춘거나 다름 없다.

  

  그래서 마지막으로 내가 생각한 테스트 케이스를 만들어서 계산을 해보니

  마지막에 -1을 해주면 계산이 딱딱 맞아 떨어지는 유레카를 발견하였다.

  

  그렇게 해서 정답이 나오게 되었다.

  진짜 시간 생각하고 문제부터 풀면 이런 꼴이 난다...

  내가 멍청하기도 하고,,,

  

  아무튼 이렇게 문제를 해결하였다!

  이런거 시간 안에 푸는 사람은 괴물이 틀림없다,,,

  자괴감이 드는 문제였다.

  

- 새롭게 알게된 내용

  1. 제발 문제부터 풀지 말자.

  2. 경우의 수는 규칙을 반드시 찾고 코딩을 시작하자

  3. HashMap의 key를 이용하여 중첩되는 값들을 제외할 수 있다.

 

- 내일 학습할 내용

  1. Map 관련 함수 복습