[프로그래머스] 의상

문제출처 : https://school.programmers.co.kr/learn/courses/30/lessons/42578

 

풀이과정

처음의 접근 : 옷 종류 별 갯수를 저장하는 배열을 생성하고, 그 배열을 백트래킹으로 탐색하며 모든 경우에 대해 계산을 진행하려 했습니다. 하지만 이렇게 하면 시간복잡도를 만족할 수 없었습니다.

 

새로운 접근에 대한 생각 : 진 부분집합에 대해 생각했습니다. 진 부분집합의 갯수는 2^n - 1 이므로, 이 문제에서 최악의 경우 n = 30이 되므로 처음의 접근과 같이 완전탐색을 진행하면 당연히 시간초과가 발생하는 것이었습니다.

 

올바른 풀이

1. 옷 종류별로 옷의 갯수를 + 1 해줘야 합니다. 여기서 +1은 (입지않음을 의미합니다)

2. +1된 옷 종류별 옷의 갯수들 끼리의 곱을 해줍니다.

3. 그 결과에 -1 한 값이 정답입니다.

 

예시
얼굴 : 안입음, 동그란 안경, 검정 선글라스
상의 : 안입음, 파란색 티셔츠
하의 : 안입음, 청바지

 

위와 같이 안입는 경우 1을 더해서 얼굴,상의,하의 모두 입는 경우의 갯수를 구하면 (안입음, 안입음, 청바지), (안입음, 파란색 티셔츠, 청바지) 이런식으로 조합이 되게됩니다. 결국 하나만 입을 때, 두 개 입을 때, ... , 모두 입을 때와 같이 모든 경우의 수를 구해줍니다. 단 (안입음, 안입음, 안입음) 의 경우는 제외해야 하기 때문에 -1을 해주는 것입니다.

 

 

알게된점

• 안입는 경우에 대해 +1을 해줌으로서 모든 조합의 갯수를 구할 수 있다는 아이디어를 배웠습니다.
• 자바 hashMap의 .getOrDefault( , ) 메서드로 key값의 존재 여부에 따른 values 셋팅을 한 번에 할 수 있음을 알게되었습니다.
• 자바의 key값을 다 가져오는 메서드는 hashmap.keySet() 이고, values 값을 다 가져오는 메서드는 hashMap.values() 임을 다시 한 번 복습했습니다.
• putIfAbsent(K key, V value) : key가 기존에 없을 때만 put이 진행됩니다. 기존에 이미 key가 존재한다면 그 key에 해당하는 value를 반환하고 새로운 value를 업데이트 하지 않습니다.

 

위 코드를 보면 putIfAbsent의 반환값은 기존의 값을 반환하며, HashMap "수박의 value는 그대로인 것을 확인할 수 있습니다.

 

전체코드

import java.util.*;

class Solution {
    
    public int solution(String[][] clothes) {
        int answer;
        
        HashMap<String,Integer> map = new HashMap<>();
        
        for(String[] c : clothes){
            map.put(c[1],map.getOrDefault(c[1],0)+1);
        }
        answer = 1;
        
        for(Integer i : map.values()){
            answer *= (i+1);
        }
        answer-=1;
        
        
        return answer;
    }
}