[Lv.2] 의상 [프로그래머스_코딩테스트] [해시] [25분]

🔍 문제 요약

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

프로그래머스

옷의 종류와 그에 맞는 옷들의 이름이 주어지고 옷의 조합을 모두 구한 값을 반환하는 문제 (각 옷의 종류에서는 하나만 선택 가능)

🧠 나의 접근 방식과 시행착오

문제를 30분 정도 풀다가 방법이 잘못된 것을 깨닫고 다른 방향으로 자고 일어나서 다시 풀어서 통과한 문제. 맨 처음에는 각 옷을 하나씩만 선택하는 것을 생각해서 모든 옷의 개수를 dict에 넣고 더한 다음  그 뒤에 다른 옷의 종류도 같이 고르는 것을 더하려고 시도했었다. 아무리 봐도 모든 케이스를 하나씩 다 구하고 있는 방법이었다 보니 실수가 나오기 좋았던 듯 하다. 그 방법은 입출력 예로 주어진 문제는 어떻게 맞아떨어져서 통과를 했었지만 테스트 케이스의 80프로 이상은 틀린 방향. 그 때쯤에 이미 25분 정도가 다 소비를 한 상태였었고 gpt가 문제 플래너를 짜달라는 것에 제대로 동작하지 않음에 씨름을 하느라 너무 머리가 돌아가지 않던 상태였던 것을 깨닫고 일단 한숨 자고 일어나서 풀기로 마음 먹음. 그 뒤로 문제를 다시 일어나서 풀 때는 생각을 전환을 해보기로 했었다. 먼저 조합을 구할 때 머리속에서 드는 생각은 aCb 와 같은 수학 공식만 떠올랐다. 일단 수학 공식을 적용하는 방법도 있겠지만 사실 수학을 가깝게 지내지 않은지 조금 된 탓에 일단 방법적으로만 그런 식으로 해보자는 생각을 가지고 문제를 다시 읽기 시작. 문제는 한 종류에 여러개의 옷이 있다고 치자. 그러면 결국 n개의 옷에서 나올 수 있는 가능성은 n + 1개라는 것을 생각했다. (선택하지 안않는 경우 1개 추가) 그렇다면 모든 옷의 종류는 n + 1과 같이 이루어지니깐 그 가능성을 모두 곱한 거에서 아무것도 선택하지 않는 단 한가지가 케이스를 빼주기만 된다는 해결책에 도달. 그렇게 푼 문제의 코드이고 결과는 모두 통과하게 되었다.

/// <summary>
/// 의상
/// https://school.programmers.co.kr/learn/courses/30/lessons/42578
/// </summary>
public int solution(string[,] clothes)
{
    // 옷 종류 별 개수 + 1 씩 한 것들의 곱의 합을 구하고 거기서 1을 뺸다
    // 개수 + 1은 해당 옷을 선택하지 않은 경우고 마지막에 1을 빼는 건 모든 옷의 종류가 선택되지 않은 케이스 1개가 들어간 것을 뺴는 것
    Dictionary<string, List<string>> dict = new Dictionary<string, List<string>>();

    for (int i = 0; i < clothes.GetLength(0); i++)
    {
        string clothName = clothes[i, 0];
        string clothType = clothes[i, 1];

        if (!dict.ContainsKey(clothType))
        {
            dict.Add(clothType, new List<string>());
        }

        dict[clothType].Add(clothName);
    }

    int res = 1;

    foreach (var pair in dict)
    {
        res *= (pair.Value.Count + 1);
    }

    return res - 1;
}

✅ 풀이 코드

코드 자체의 흐름은 필자가 푼 방법이 맞았기에 좀 더 필요 없는 것을 간략화한 피드백을 받아서 적어두었다. (옷의 이름을 리스트에 넣을 필요 없이 개수만 넣으면 된다는 점)

Dictionary<string, int> dict = new Dictionary<string, int>();

for (int i = 0; i < clothes.GetLength(0); i++)
{
    string clothType = clothes[i, 1];

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

int res = 1;
foreach (var count in dict.Values)
{
    res *= (count + 1);
}

return res - 1;

🔄 정리

조합을 구하는 문제라면 꼭 필요한 핵심적인 요소가 들어있는 문제라고 생각한다. 각 기회의 수 + 1을 해서 각 수치들을 곱한 다음 절대 나올 수 없는 기회 n 개를 빼는 형태를 기억해두면 다른 조합의 문제에서도 유용하게 쓸 수 있을 듯 하다.