강의로 돌아가기
김대호

첫번째 케이스가 시간초과 뜨네요

다른 케이스는 모두 통과되는데 1번째 케이스 만 시간초과가 떠서 실패가 되네요.

혹시 어느 부분이 잘못 됐는 지 알려주세요!

감사합니다.

import java.util.HashMap;

class Solution {
    public int solution(String[][] clothes) {
        int answer = 0;
        int typeNum = 0;
        HashMap<String,Integer> map = new HashMap<>();

        for(int i=0; i<clothes.length; i++) {
            String name = clothes[i][0];
            String type = clothes[i][1];

            if(!map.containsKey(type)){
                typeNum++;
                map.put(type, 0);
            }
            map.put(type, map.get(type)+1);
        }

        // 종류별 옷의 개수를 배열로 저장
        int[] size = new int[typeNum]; int j=0;
        for(String str : map.keySet()){
            size[j++] = map.get(str);
        }

        // 비트 배열을 이용하여 총 가지 수 구함
        for(int i=1; i<Math.pow(2,typeNum); i++){
            int num = i; int idx = 0;
            int a = 1;  // 현재 비트의 가지 수             
            while(num>1){
                if(num%2 == 1){
                    a = a*size[idx];
                }
                idx++;
                num = num/2;
            }
            if(num==1)
                a = a*size[idx];
            answer += a;
        }
        return answer;
    }
}
1 개의 답변
지양호

가능한 모든 조합을 직접 구해서 계산할 필요가 없습니다.
예를들어 머리:3, 얼굴:2, 옷:1 이라면 총 가능한 개수는

(3+1) * (2+1)*(1+1) -1 = 13

+1씩을 더한 것은 착용하지 않은 경우가 추가 되기 때문이고 마지막으로 -1을 한것은 모든 부위를 입지 않은 경우는 없기 때문입니다.

  • 이시윤
    와 진짜 간단한 경우의수 문제인데 이걸 보기전까진 아예 생각도 못함 ㄷㄷ 지양호님 대단하시네요 이시윤 2018.09.30 20:58
  • 이선범
    와........저도 모든 조합 계산하려고 뇌 풀가동 하고 있었는데.....왜 이걸 생각 못했지.................. 감사합니다ㅠㅠㅠㅠ 이선범 2018.10.03 05:05
  • 이선범
    바로 풀렸네요 하악 감사합니다ㅠㅠ 이선범 2018.10.03 05:10
  • 한진욱
    짱입니다 ㅠㅠ 한진욱 2018.10.15 16:49
  • anonymity0609
    감사합니다!!!! anonymity0609 2018.10.23 16:27
  • Kangaroo
    감사합니다! Kangaroo 2018.11.01 17:37
  • 배효준
    아 옷 종류라는 것이 순서가 있는 거니깐 순열이 맞네요....하.... 어렵다ㅠㅠ 배효준 2018.11.06 17:00
  • 박성환
    정말 대단하신분.. 박성환 2018.11.16 21:18
  • 최서현
    와 진짜 감사합니다 ! 최서현 2018.12.30 20:54
  • 한원근
    저 식 결과가 왜 13이나오는거에여? 23아님? 한원근 2019.04.18 19:22
답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.