[프로그래머스]해시:위장(java)

문제보러가기

코딩테스트 연습 - 위장

이 문제는 나의 수학 기억력이 이 정도라니... 라는걸 깨닫게 한 문제였다. 조합이길래 조합 코드 만들어서 사용했는데 시간 초과!!!! 모든 조합수 구하면 안 돼요~

 

 

 

문제풀이

-각각의 key, value로 저장할 수 있는 자료구조인 Map을 이용해 저장한다

      -> key : 의상의 종류 , value : 의상 이름 *value가 여러 개일 수 있으므로 리스트로 저장한다

-같은 key의 의상끼리는 조합을 만들 수 없고 다른 key끼리가 조합이 가능하며 하나만 입는 경우는 있으나 하나도 안 입는 경우는 없다

-경우의 수를 구해보면 

A, B, C종류(key)의 의상이 있고 A, B, C가 각각의 종류에 해당하는 의상 개수(value)일 때

식 : (A+1)(B+1)(C+1)-1

-> 여기서 확률의 경우의 수 개념이 필요하다!

-> 곱의 법칙 개념을 생각해보면 A가 일어날 경우 * B가 일어날 경우 = A와 B가 동시에 일어날 경우

        ex) 바지 2개 티셔츠 3개 -> 옷의 조합 = 2*3 =6 이 되겠죠!

-식에서 각각에 +1을 해주는 이유 : A종류의 옷 중에서 아예 선택을 안 하는 경우도 있으므로 A 의상 종류가 만약 3개라면 4가지의 경우의 수를 갖게 되는 것

-식에서 마지막에 -1을 해주는 이유 : A, B, C 모든 옷을 선택을 안 하는 경우는 제외되므로 한 가지의 경우를 빼준다

-혹시 A+B+C+AB+AC+BC+ABC의 식을 먼저 발견하고 구한 경우!

 

->이렇게 인수분해를 하면 경우의 수 와 같은 식이 결과로 나타나는 것을 알 수 있다

 

 

사실 내가 이해가 안 됐었던 거라.. 정확하게 이해하고자 길게 길게 상세히 적어보았다 ㅎ..

 

import java.util.ArrayList;
import java.util.HashMap;
class Solution {
    public int solution(String[][] clothes) {
        int answer=1;
        HashMap<String, ArrayList<String>> map = new HashMap<>();
		for (int i = 0; i < clothes.length; i++) {
			ArrayList<String> list;
			if (map.containsKey(clothes[i][1])) {
				list = map.get(clothes[i][1]);

			} else {
				list = new ArrayList<>();
			}
			list.add(clothes[i][0]);
			map.put(clothes[i][1], list);
		}
        for(String key : map.keySet()){
            answer *= (map.get(key).size()+1);
        }
        return answer-1;
    }
}

 

 

 

 

--이거는 1번 케이스가 시간 초과가 나서 실패한 조합을 구하는 코드 

package programers;

import java.util.ArrayList;
import java.util.HashMap;

public class Camouflage {

	static int answer = 0;
	static HashMap<String, ArrayList<String>> map;
	public static void main(String[] args) {
		String[][] clothes = { { "crow_mask", "face"}, {"blue_sunglasses", "face"}, {"smoky_makeup", "face" } };
		/**
		 * 아래에는 시간초과 난 코드
		 */
		map = new HashMap<>();
		for (int i = 0; i < clothes.length; i++) {
			ArrayList<String> list;
			if (map.containsKey(clothes[i][1])) {
				list = map.get(clothes[i][1]);

			} else {
				list = new ArrayList<>();
			}
			list.add(clothes[i][0]);
			map.put(clothes[i][1], list);
		}
	        boolean[] visited = new boolean[map.keySet().size()];
	        String[] keys = new String[map.keySet().size()];
	        int index=0;
	        for(String key : map.keySet()) {
	        	keys[index++] = key;
	        }
	        for (int i = 1; i <= map.keySet().size(); i++) {
	            combination(keys, visited, 0, map.keySet().size(), i);
	        }

		System.out.println(answer);

	}
	static void combination(String[] keys, boolean[] visited, int start, int n, int r) {
	    if(r == 0) {
	    	answer++;
	        return;
	    } 
	    for(int i=start; i<n; i++) {
	        visited[i] = true;
	        String key = keys[i];
	        for(int j=0;j<map.get(key).size();j++) {
	        	combination(keys, visited, i + 1, n, r - 1);	        	
	        }
	        	
	        visited[i] = false;
	    }
		
		
	}
	


}