[TIL] C# 프로그래머스 _ 알고리즘(해시) 문제

1. 문제

코니는 매일 다른 옷을 조합하여 입는것을 좋아합니다.
코니는 각 종류별로 최대 1가지 의상만 착용할 수 있으며 하루에 최소 한 개의 의상을 입습니다
착용한 의상의 일부가 겹치더라도, 다른 의상이 겹치지 않거나, 혹은 의상을 추가로 더 착용한 경우에는 서로 다른 방법으로 옷을 착용한 것으로 계산합니다.
코니가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

 

2. 문제 핵심 정리

1) 같은 종류의 옷은 동시 착용이 불가함으로 종류별로 1개만 선택 가능

2) 착용하지 않는 경우의 수도 있으므로 의상 종류별로 경의 수를 +1 함

3) 아무것도 안 입는 경우는 제외해야 함으로 전체 경우의 수에서 -1을 함

※ 최종 경우의 수 = ( 해당 종류의 의상 개수 + 1) x (다른 종류의 의상 개수 +1) - 1

 

3. 풀이 방법 및 코드 작성

1) 딕셔너리로 카테고리별 옷 개수 저장 -> Dictionary<string, int>

2) foreach로 경우의 수 계산 후 -1 

using System;
using System.Collections.Generic;

public class Solution {
    public int solution(string[,] clothes) {
        Dictionary<string, int> dict = new Dictionary<string, int>();
        
        for (int i = 0; i < clothes.GetLength(0); i++) {
            string name = clothes[i, 0];
            string category = clothes[i, 1];
            
            if (!dict.ContainsKey(category)) {
                dict[category] = 0;
            }
            dict[category]++;
        }
        
        int answer = 1;
        foreach (var item in dict) {
            answer *= (item.Value + 1); 
        }
        
        return answer - 1; 
    }
}

 

if (!dict.ContainsKey(category)) {
    dict[category] = 0;
}
dict[category]++;

• 딕셔너리에 아직 해당 종류(category)가 없으면 dict["종류"] = 0; 으로 초기화
• 해당 종류의 의상 개수를 1 증가시켜 같은 종류에 속한 옷이 몇 개인지를 카운트