[알고리즘 문제풀이] 프로그래머스 - 위장

yourjin·2022년 2월 27일

level2 알고리즘 해시(Hash)

알고리즘 문제풀이

목록 보기

14/28

TIL (2022.02.16)

➕ 오늘 푼 문제

프로그래머스 - 위장

➕ 아이디어

의상의 종류를 key로, 의상 이름을 value로 둔 해시를 만든다.
- value는 해시 이름 대신 해시 개수로 둬도 좋다.
모든 key를 탐색하며, 해당 값에서 선택할 수 있는 모든 경우의 수를 누적하여 곱해준다.
- 각 key 마다는 value 중 한 개를 선택하거나, 아무것도 선택하지 않을 수 있다. 따라서 모든 경우의 수는 value의 개수 + 1(아무것도 선택하지 않은 경우) 이다.
최소한 1개 이상의 옷을 입는다는 문제 조건으로 인해 모든 key를 선택하지 않는 경우는 한 가지는 제외한다. 따라서 최종 결과에 -1을 해준다.

➕ Java 코드

import java.util.*;

class Solution {
    public int solution(String[][] clothes) {
        int answer = 1;
        HashMap<String, Integer> closet = new HashMap<>();
        
        for(int i=0; i<clothes.length; i++){
      		String key = clothes[i][1];    
            closet.put(key, closet.getOrDefault(key, 0) + 1);
       }
        
    	Iterator<Integer> it = closet.values().iterator();
    	while(it.hasNext()){	
            answer *= it.next().intValue() + 1;
        }
        return answer - 1;
    }
}

➕ Python 코드

def solution(clothes):
    answer = 1
    closet = {}
    
    for cloth, category in clothes:
        if category in closet.keys():
            closet[category].append(cloth)
        else:
            closet[category] = [cloth]
    
    for key in closet.keys():
				# 각 key마다 (value + 1)가지를 선택할 수 있으므로 이를 곱해준다.
        answer *= len(closet[key]) + 1
        
    return answer - 1