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

문제 원본: 프로그래머스 링크 (코딩테스트)

카테고리: 해시

 

문제 설명

2차원 배열로 clothes가 있다. 배열의 각 요소는 ["의상의 종류", "의상의 이름"]의 형태로 이루어져 있다. 주어진 요소를 조합해서 나올 수 있는 모든 경우의 수를 구해야 한다. 아래는 예시이다. 

String[][] clothes = {{"yellow_hat", "headgear"}, {"blue_sunglasses", "eyewear"}, {"green_turban", "headgear"}};

위의 예시의 결과값은 5이다. 아래는 선택 가능한 모든 경우다.

1. yellow_hat

2. blue_sunglasses

3. green_turban

4. yellow_hat + blue_sunglasses

5. green_turban + blue_sunglasses

조건

- 주어진 배열의 요소 중 최소한 한 가지 이상은 선택해야 한다.

- 순서는 고려하지 않는다.

 

제한사항

- 스파이가 가진 의상의 개수는 1개 이상 30개 이하이다.

- 같은 이름을 가진 의상은 없다.

- 최소 하나의 의상을 선택해야 한다.

- clothes의 모든 원소는 문자열로 이루어져 있다.

- 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알팝멧 소문자 또는 '_'로만 이루어져 있다.

 

내 풀이 과정

- 각 의상의 종류별로 HashMap에 저장하여 종류별 의상의 개수를 저장해야 한다.

- 똑같은 이름을 가진 의상이 없으니 고려해야하는 경우가 적을 것이다.

- 의상을 하나씩만 착용했을 경우 + 각 의상을 서로 조합한 경우의 수

 

먼저 문제 풀이 전에 위와 같이 틀을 잡고 문제에 접근했으나 명확한 풀이를 생각해 내기가 어려웠다. 

의상을 하나씩만 착용했을 경우는 전체 의상의 개수와 같으니 쉽다. 하지만 그 외의 모든 경우의 수를 리턴하는 로직을 짜는 것이 좀 까다로웠다. 의상의 종류가 3개라면 2개 선택한 경우의 수와 3개를 선택한 경우의 수를 구해야 했다. 문제는 의상의 종류의 수가 바뀐다는 것이다. for문 설계를 고민하다가 마음에 들지 않지만 아래와 같은 코드를 먼저 작성했다. 의상 종류의 최대값이 4라고 가정했다. 그야말로 단순 무식한 로직이다.

내 풀이 (실패함)

public int solution(String[][] clothes) {
        int answer = 0;

        HashMap<Object, Integer> map = new HashMap<>();
        for (String[] cloth : clothes)
            map.put(cloth[1], map.getOrDefault(cloth[1], 0) + 1);

        Object[] categories = map.keySet().toArray();
        answer += clothes.length;

        if (map.size() >= 2) {
            for (int i = 0; i < map.size() - 1; i++) {
                for (int j = i + 1; j < map.size(); j++) {
                    answer += (map.get(categories[i]) * map.get(categories[j]));
                }
            }
        }

        if (map.size() >= 3) {
            for (int i = 0; i < map.size() - 2; i++) {
                for (int j = i + 1; j < map.size() - 1; j++) {
                    for (int k = j + 1; k < map.size(); k++) {
                        answer += (map.get(categories[i]) * map.get(categories[j]) * map.get(categories[k]));
                    }
                }
            }
        }

        if (map.size() >= 4) {
            for (int i = 0; i < map.size() - 3; i++) {
                for (int j = i + 1; j < map.size() - 2; j++) {
                    for (int k = j + 1; k < map.size() - 1; k++) {
                        for (int l = k + 1; l < map.size(); l++) {
                            answer += (map.get(categories[i]) * map.get(categories[j]) * map.get(categories[k]) * map.get(categories[l]));
                        }
                    }
                }
            }
        }

        return answer;
    }

 

예시 문제 2개는 무사 통과했으나, 실제 채점 결과는 28개의 테스트 케이스 중 46%만 통과되었다. 소요 시간을 봐서는 시간이 오래걸려 실패한 것은 아니었다. 풀이가 잘못된 것이다. 얻어 걸리길 바랐던 것이 잘못이었다. 분명 의상 종류의 최댓값은 4가 아닐 것이다. 

 

채점 결과

 

결국 이 문제는 한 시간 넘게 풀다가 포기하고 다른 사람의 풀이를 찾아보았다. (출처)

다른 사람의 풀이 1

public int solution(String[][] clothes) {
        int answer = 1;
        HashMap<String, Integer> map = new HashMap<>();

        for (String[] clothe : clothes) {
            map.put(clothe[1], map.getOrDefault(clothe[1], 0) + 1);
        }

        Set<String> keySet = map.keySet();
        for (String key : keySet)
            answer *= map.get(key) + 1; // 해당 종류의 옷을 안입는 경우를 고려 (이것이 핵심이다.)

        return answer - 1; // 아무것도 안 입은 경우를 제거
    }

생각보다 단순하고 쉬운 부분을 내가 미처 생각못했다. 나는 하나씩만 선택한 경우의 수 모든 선택 가능한 경우의 수를 각각 구해서 더하려고 했다. 그러나 정말 쉬운 방법이 있었다. 

 

for문에서 해당 종류의 옷을 안입는 경우를 고려해서 값을 구한 다음에 마지막에 모든 옷을 안입는 경우의 수를 빼면 되는 것이다. 얼마나 명쾌한지. 한 시간 넘게 고민하던 문제를 이렇게 명쾌하게 풀어놓은 답을 볼 때면 상쾌함과 아쉬움의 마음이 동시에 든다.

 

채점을 해보니 연산 시간도 우수한 것 같다. 

 

다른 사람의 풀이 2

제출을 하면 가장 많은 추천을 받은 풀이가 최상단에 보인다. 흥미로워서 첨부한다.

public int solution(String[][] clothes) {
        return Arrays.stream(clothes)
                .collect(groupingBy(p -> p[1], mapping(p -> p[0], counting())))
                .values()
                .stream()
                .reduce(1L, (x, y) -> x * (y + 1))
                .intValue() - 1;
    }

stream을 이용해서 코드를 상당히 간결하게 만들었다. 많은 사람들이 댓글로 감탄을 표현했다. 궁금한 마음에 위 코드를 채점해보았다. 코드는 짧지만 성능은 어떨지 궁금했다. 보이기에는 단순해도 내부 API를 복잡하게 사용하는 것으로 보였다. 

채점 결과 성능은 이전 코드에 비해 훨씬 안좋았다. 이전 코드의 테스트 당 소요 시간이 0.1ms 미만이었던 것에 비해 위 코드의 소요시간은 평균 7ms가 소요되었다. 대략 80배 정도 느린 것이다. 자바8의 API를 사용해서 코드를 단순하게 만들어 보기에는 좋지만 그것이 꼭 좋은 것은 아니었다. 

 

참고

- 알고리즘 풀이 깃허브 저장소