[코딩테스트] Programmers - 의상 (실패)

 

https://school.programmers.co.kr/learn/courses/30/lessons/42578

프로그래머스

 

 

풀이

문제 분류가 해시로 되어 있어서 Dictionary로 풀어보려고 했다. 

손으로 풀어보니.. 

내가 생각한 서로 다른 옷의 조합의 수는 "모든 의상의 개수 + (headgear의상 개수 * eyewear의상 개수 * ... * )"이다. 

이대로 코드를 짜봤다. 

 

코드1 - 오답

public int solution(string[,] clothes) 
    {
        int answer = 0;
        
        Dictionary<string, int> dict = new Dictionary<string, int>();
        for(int i = 0; i < clothes.GetLength(0); i++)
        {
            if(!dict.ContainsKey(clothes[i,1]))
            {
                dict.Add(clothes[i,1], 1);
            }
            else
            {
                dict[clothes[i,1]]++;
            }
            answer++;
        }

        if(dict.Count > 1)
        {
            int mul = 1;
            foreach(string key in dict.Keys)
            {
                mul *= dict[key];
            }
            
            answer += mul;
        }
        
        
        return answer;
    }

예시 2에서 오답이라고 나온다. 

"모든 의상의 개수 + (headgear의상 개수 * eyewear의상 개수 * ... * )" 이 공식대로라면 3 + 3 = 6이다. 

그러나 예제2의 정답은 의상 종류가 1개만 있으니 3이다. 

따라서 저 공식은 잘못되었고 잘못된 공식으로 코드를 짰으니 틀렸다. 

 

 

풀이 2

혼자서 도저히 못 풀겠어서 Gemini에게 물어봤다. 

옷 종류 하나씩 경우의 수를 헤아리고 마지막에 경우의 수들을 모두 곱하는 방식이었다. 

 

예제 1을 보자. 

headgear가 2개(yellow_hat, green_turban), eyewear가 1개(blue_sunglasses)이다. 

옷은 종류별로 최대 1가지 의상만 착용할 수 있다. 

 

headgear부터 보자. 

• yellow_hat만 입는 경우
• green_tuaban만 입는 경우
• 아무것도 입지 않는 경우 

 

eyewear를 보자. 

• blue_sunglasses만 입는 경우
• 아무것도 입지 않는 경우

 

서로 다른 옷의 조합 수 = 3 * 2 = 6

그런데 문제에서 "하루에 최소 한 개의 의상은 입습니다."라고 했다. 이 말은 아예 아무것도 입지 않는 경우는 없다는 것이다. 

그러니 6에서 1을 빼면 된다. 따라서 서로 다른 옷의 조합 수는 5가 된다. 

 

서로 다른 옷의 조합 수를 공식화하면 다음과 같다. 

(옷 종류 A의 개수 + 1) * (옷 종류 B의 개수 + 1) * ... -1 

-> 여기서 +1의 1은 아무것도 입지 않는 경우의 수이며, -1은 아무것도 입지 않는 경우를 뺀 것이다. 

 

저 공식을 참고해서 코드를 짜면 된다. 

 

 

코드 2 - 정답

using System;
using System.Collections.Generic;

public class Solution {
    public int solution(string[,] clothes) 
    {
        int answer = 0;
        
        Dictionary<string, int> dict = new Dictionary<string, int>();
        for(int i = 0; i < clothes.GetLength(0); i++)
        {
            if(!dict.ContainsKey(clothes[i,1]))
            {
                dict.Add(clothes[i,1], 1);
            }
            else
            {
                dict[clothes[i,1]]++;
            }
        }
        
        int mul = 1; 
        foreach(string key in dict.Keys)
        {
            mul *= (dict[key] + 1);
        }
        answer = mul - 1; 
        
        return answer;
    }
}

 

 

복습 1 풀이 (6/8)

[문제]
코니는 매일 다른 옷을 조합하여 입는다. 
각 종류별로 최대 1가지 의상만 착용할 수 있다. 
하루에 최소 한 개의 의상은 입는다. 

[입력]
코니가 가진 의상들 2차원 배열 clothes 

[출력]
서로 다른 옷의 조합의 수 return 

[제한사항]
- clothes 각 행은 [의상의 이름, 의상의 종류] 
- 1 <= 코니가 가진 의상 수 <= 30
- 같은 이름 의상 존재 X
- clothes 모든 원소는 문자열
- 1 <= 모든 문자열의 길이 <= 20, 알파벳 소문자 또는 _로 이루어짐. 

[풀이1] -> 실패
- 딕셔너리에 clothes 넣기 (key = string(옷 종류), value = int(옷 개수))
- 딕셔너리에 있는 key들 갯수 + (옷 개수들 곱)을 반환 

[풀이2] -> 실패 
- 딕셔너리에 clothes 넣기. 
- 딕셔너리에 있는 value 총합 + 2개씩 뽑는 경우 + 3개씩 뽑는 경우 + ... 를 반환 

 

 

코드 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++)
        {
            if(!dict.ContainsKey(clothes[i, 1]))
                dict.Add(clothes[i, 1], 1);
            else
                dict[clothes[i, 1]]++;
        }
        
        int keyCount = 0; 
        int count1 = 0; 
        int mul = 1;
        foreach(string key in dict.Keys)
        {
            keyCount++;
            count1 += dict[key];
            mul *= dict[key];
        }

        if(keyCount == 1)
            return count1;
        
        return count1 + mul;
    }
}

 

 

코드 2 - 실패 

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public int Combination(int a, int b)
    {
        int mul1 = 1; 
        for(int i = a; i >= 1; i--)
            mul1 *= i;

        int mul2 = 1;
        for(int i = b; i >= 1; i--)
            mul2 *= i;

        return mul1 / mul2;
    }

    public int solution(string[,] clothes)
    {
        Dictionary<string, int> dict = new Dictionary<string, int>();
        for(int i = 0; i < clothes.GetLength(0); i++)
        {
            if(!dict.ContainsKey(clothes[i, 1]))
                dict.Add(clothes[i, 1], 1);
            else
                dict[clothes[i, 1]]++;
        }

        int result1 = dict.Values.Sum();
        int result2 = 0; 
        int keyCount = dict.Keys.Count;
        for(int i = 2; i <= keyCount; i++)
            result2 += Combination(keyCount, i);

        return result1 + result2;
    }
}

 

옷 종류가 다 다른 경우 위 코드들은 오답을 반환한다. 

 

 

코드 3 - 성공

public int solution(string[,] clothes)
    {
        Dictionary<string, int> dict = new Dictionary<string, int>();
        for(int i = 0; i < clothes.GetLength(0); i++)
        {
            if(!dict.ContainsKey(clothes[i, 1]))
                dict.Add(clothes[i, 1], 1);
            else
                dict[clothes[i, 1]]++;
        }
        
        int mul = 1; 
        foreach(string key in dict.Keys)
            mul *= (dict[key] + 1);
        
        return mul - 1; 
    }

 

예전에 작성한 코드를 봤다. 

옷 종류별로 모든 경우의 수를 구해서 곱하면 된다고 한다. 

A종류 옷이 2개라면 A-1을 입는 경우, A-2을 입는 경우, 아무것도 입지 않는 경우가 있고

B종류 옷이 3개라면 B-1을 입는 경우, B-2을 입는 경우, B-3을 입는 경우, 아무것도 입지 않는 경우가 있다. 

 

A종류 옷과 B종류 옷을 입는 경우의 수는 3 * 4 = 12가지이다. 

그런데 문제에서 아무것도 입지 않는 경우는 없다고 했으므로, 12 - 1 = 11가지이다.