[프로그래머스] 위장 - Java(Feat. 삽질 주의)

문제 설명

 

코딩테스트 연습 - 위장

 

 

풀이 회고

이번 문제는 오랫동안 고민하다가 결국에는 힌트(Hint)를 보고야 말았습니다. 먼저 이 문제를 해결하기 위한 당초 저의 접근 방법은 옷을 1개만 선택하는 경우, 2개만 선택하는 경우, 3개만 선택하는 경우(최대 옷의 종류의 개수) 등 각각의 경우별로 옷을 "조합(combination)"할 수 있는 모든 경우의 수를 구하고자 했었습니다. 문제에서 주어진 예시에 적용해보면 다음과 같습니다.

 

 

문제 설명에서 주어진 입출력 예시들 한해서는 위와 같은 접근 방법으로 간신히 "구현"할 수는 있었습니다. 다만, 구현하면서도 소스 코드가 점점 길어지는 것을 보면서 "지금 뭔가 잘못되어가고 있다는 것"을 본능적으로 느낄 수 있었습니다... 😇 해당 소스 코드는 다음과 같습니다.

 

// 아래 풀이는 계속 삽질을 하다가 결국 포기 및 방치된 소스 코드 입니다 😂

public int solution(String[][] clothes) {

        int countOfClothes = clothes.length; // 전체 옷 중 하나씩 입는 경우의 수

        int result = countOfClothes;

        Map<String, Integer> map = new HashMap<>();

        for (String[] cloth : clothes) { // 종류별 옷의 개수
            map.put(cloth[1], map.getOrDefault(cloth[1], 0) + 1);
        }

        int countOfSort = map.size();

        if (countOfSort > 1) { // 종류가 2개 이상인 경우
            boolean flag;
            int countOfCases;
            int temp;
            int cnt;

            for (int i = 2; i <= countOfSort; i++) {

                flag = true;
                countOfCases = 1;
                temp = 0;
                cnt = 0;

                for (String s : map.keySet()) {
                    if (map.get(s) > 1) {
                        countOfCases *= combination(map.get(s), 1);
                        cnt++;
                        flag = false;
                    }
                    else {
                        temp++;
                    }
                }

                if (flag == false) {
                    if (temp >= i - cnt) {
                        countOfCases *= combination(temp, i - cnt);
                        result += countOfCases;
                    }

                    if (temp >= i)
                        result += combination(temp, i);
                }
                else {
                    result += combination(countOfSort, i);
                }
            }
        }

        return result;
    }
    
    public int combination(int n, int r) {
        if(n == r || r == 0)
            return 1;
        return combination(n - 1, r - 1) + combination(n - 1, r);
    }

 

 

우선 옷을 1개만 선택하는 경우는 단순히 옷의 종류와 상관없이 단지 옷의 개수와 동일합니다. 다만 옷의 종류가 2개 이상일 경우에는 "조합"을 해야하는 일이 발생합니다. 그리하여 옷의 종류의 최소 개수를 2로 두어(개수 1은 앞서 구했으므로) 옷의 최대 개수만큼 for 반복문을 두었고 해당 for 반복문 내에서 종류별 옷의 개수에 따라 조합을 구하도록 로직을 구현했습니다.

 

해당 로직은 입출력 예시들에 대해서는 모두 정상적으로 기댓값이 나오는 것을 확인할 수 있었지만 문제에서 요구하는 "모든" 경우에 대한 기댓값을 도출할 수는 없었습니다. 특히 종류별 옷의 개수가 1개씩만 있을 때는 정답을 구할 수 있었지만 문제는 종류별 옷의 개수가 2개 이상인 경우가 존재하는 경우에 잘못된 값 출력 내지 오류(스택오버플로우 등)의 문제가 발생되곤 했습니다. (단, 문제에서 주어진 입출력에 대해서는 정답 도출)

 

이는 당연하게도 주어진 입출력 예시에 초점을 두어 구현했으므로 주어진 종류별 옷의 개수에 따라 특정 개수만큼 선택하는 "조합"에 대한 로직이 제대로 구현되지 않았기 때문입니다. 하지만 이를 구현하기는 매우 까다로웠습니다. 옷의 종류가 "모자", "상의", "하의" 총 3종류라고 할 때 각각의 종류별로 서로 다른(문제 조건) 옷이 2개씩 있다고 가정해보겠습니다. 옷을 1개~3개만 선택했을 때 옷의 조합의 경우의 수를 "조합(combination)"으로 나타내면 다음과 같습니다.

 

 

예를 들어, 2개만 선택하는 경우에는 3가지 종류 중 2 종류를 선택하여 각각의 종류의 옷 중 한개씩을 선택하도록 구현해야했는데, 문제는 이에 대한 조합(combination)은 종류별 옷의 개수가 다를 때마다 제각각이었다는 점(일종의 규칙성을 찾기가 까다로움)이었습니다. 그리하여 현재의 문제 접근 방법은 포기하고 결국에는 그만 힌트를 보고야 말았습니다...😥

 

 

새로운 문제 접근 방식은 굉장히 단순 명료했습니다. 결과적으로는 종류별 옷의 개수에 +1 연산을 해준 다음 이를 모두 곱한 후 최종적으로 -1을 해주면 그게 바로 정답이었습니다. 이때 왜 종류별 옷의 개수에 +1을 해주냐면 해당 종류의 옷 자체를 안 입을 수도 있기 때문에 이 경우의 수를 더해준 것입니다. 이를 모든 종류별 옷의 개수에 다 적용시켜준 후 전체를 다 곱해주면 스파이가 옷을 조합할 수 있는 모든 경우의 수가 나오게 됩니다. 하지만 -1을 해주어야 하는데 문제의 제한사항으로 "스파이는 최소 한 개의 의상을 입는"다고 했기 때문입니다. 이를 그림으로 도식화 해보면 다음과 같습니다. 

 

 

소스 코드(Success)

    public int solution(String[][] clothes) {
        int result = 1;

        Map<String, Integer> map = new HashMap<>();

        for (String[] cloth : clothes) { // 종류별 옷의 개수
            map.put(cloth[1], map.getOrDefault(cloth[1], 0) + 1);
        }

        for (int i : map.values()) {
            result *= (i+1);
        }

        return result - 1;
    }

 

오늘의 교훈

알고리즘 문제는 안 되겠다 싶으면 오랜 시간 허비하지 말고 힌트를 보자 😇

 

 

 

 

참고자료

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