문제

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

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int solution(String[][] clothes) {
    Map<String, Integer> map = new HashMap<String, Integer>();

    for (String[] s : clothes) {
        int value = 1;
        String key = s[1];
        if (map.containsKey(key)) {
            value = map.get(key);
        }

        map.put(key, ++value);
    }

    int answer = 1;
    for (Map.Entry<String, Integer> entry : map.entrySet()) {
        answer *= entry.getValue();
    }

    return answer - 1;
}

흐름

  1. [[“yellow_hat”, “headgear”], [“blue_sunglasses”, “eyewear”], [“green_turban”, “headgear”]], clothes안에 이런 식으로 옷이름, 종류 로 저장되어 있으므로 chothes 크기 만큼 반복하면서 옷 종류를 꺼냄

  2. 옷 종류를 key로 하는 Map이 있는 지 확인

  3. 있으면 값을 증겨 시켜야 하므로 value를 꺼내옴

  4. ++해서 값을 증가 시켜서 저장하고, 없으면 해당 key로 새로 저장

  5. 순열과 조합 공식을 바탕으로 value를 모두 곱함

  6. 문제에서 최소 1 개의 옷은 입는다고 하였으므로, 옷을 모두 안입는 경우를 제외하기 위해 -1을 함

  7. 끝

조합 공식

Every interaction is both precious and an opportunity to delight.

서로 다른 n개의 원소에서 순서에 상관없이 r개를 뽑을 때, 이를 n개에서 r개를 택하는 조합이라고 한다. 이 조합은 순열과 다른 개념으로 순서 차이가 중요하다.

$$ nCr = nPr / r! = n! / (n-r)!r! $$

  • 이 공식으로 위 문제를 풀어보면 헤어 2개, 안경 1개 이므로
  • 헤어 2개에서는 입을경우, 안 입을 경우 2 가지이고 이를 수식으로 표현하면
  • 0개를 뽑는 경우 = $$ 2C0 = 2P0 / 0! = 2! / (2-0)!0! = 2 / 2 = 1 $$
  • 이 되고, 나머지의 경우도 계산하면 $$ 1 + 2 = 3 $$ 이 된다.
  • 안경도 마찬가지로 입을 경우, 안 입을 경우 2 가지로
  • $$ 1C0 + 1C1 = 1 + 1 = 2 $$ 가 되고
  • 마지막으로 둘 다 안 입는 경우는 없으므로 -1을 하면
  • $$ 3 * 2 - 1 = 5 $$가 된다

다른 분의 코드

1
2
3
4
5
6
7
public int solution(String[][] clothes) {
    return Arrays.stream(clothes)
            .collect(groupingBy(p -> p[1], mapping(p -> p[0], counting())))
            .values()
            .stream()
            .collect(reducing(1L, (x, y) -> x * (y + 1))).intValue() - 1;
}
  • 람다식 대박

결과

1번

번호 속도
테스트 1 통과 (0.93ms, 50.5MB)
테스트 2 통과 (0.85ms, 51.9MB)
테스트 3 통과 (0.86ms, 51.9MB)
테스트 4 통과 (0.93ms, 52.8MB)
테스트 5 통과 (0.80ms, 52MB)
테스트 6 통과 (0.88ms, 50.5MB)
테스트 7 통과 (0.84ms, 52.2MB)
테스트 8 통과 (0.85ms, 52.8MB)
테스트 9 통과 (0.86ms, 51.9MB)
테스트 10 통과 (0.87ms, 52.2MB)
테스트 11 통과 (0.89ms, 52.4MB)
테스트 12 통과 (0.82ms, 51.9MB)
테스트 13 통과 (0.81ms, 52.3MB)
테스트 14 통과 (0.75ms, 51.9MB)
테스트 15 통과 (0.82ms, 50.5MB)
테스트 16 통과 (0.91ms, 50.5MB)
테스트 17 통과 (0.90ms, 52.5MB)
테스트 18 통과 (0.88ms, 52.1MB)
테스트 19 통과 (0.88ms, 51.8MB)
테스트 20 통과 (0.90ms, 52.4MB)
테스트 21 통과 (0.80ms, 52.9MB)
테스트 22 통과 (0.86ms, 51.6MB)
테스트 23 통과 (0.80ms, 50.7MB)
테스트 24 통과 (0.90ms, 50.3MB)
테스트 25 통과 (0.90ms, 52.3MB)
테스트 26 통과 (0.93ms, 52.1MB)
테스트 27 통과 (0.86ms, 52.3MB)
테스트 28 통과 (0.90ms, 50.1MB)

2번

번호 속도
테스트 1 통과 (14.41ms, 53.2MB)
테스트 2 통과 (12.19ms, 52.8MB)
테스트 3 통과 (12.05ms, 52.9MB)
테스트 4 통과 (13.03ms, 50.9MB)
테스트 5 통과 (14.21ms, 50.9MB)
테스트 6 통과 (12.85ms, 51MB)
테스트 7 통과 (13.19ms, 50.9MB)
테스트 8 통과 (13.32ms, 53.6MB)
테스트 9 통과 (13.37ms, 53.1MB)
테스트 10 통과 (12.58ms, 53.2MB)
테스트 11 통과 (12.34ms, 52.7MB)
테스트 12 통과 (13.69ms, 52.4MB)
테스트 13 통과 (13.19ms, 52.7MB)
테스트 14 통과 (12.48ms, 51.1MB)
테스트 15 통과 (11.82ms, 52.5MB)
테스트 16 통과 (12.63ms, 52.7MB)
테스트 17 통과 (13.37ms, 53.1MB)
테스트 18 통과 (13.54ms, 53.1MB)
테스트 19 통과 (13.20ms, 50.7MB)
테스트 20 통과 (13.11ms, 52.7MB)
테스트 21 통과 (12.80ms, 52.6MB)
테스트 22 통과 (13.48ms, 53.2MB)
테스트 23 통과 (12.59ms, 52.5MB)
테스트 24 통과 (13.71ms, 50.9MB)
테스트 25 통과 (12.94ms, 52.4MB)
테스트 26 통과 (13.67ms, 50.9MB)
테스트 27 통과 (13.75ms, 53MB)
테스트 28 통과 (13.04ms, 51.7MB)

테스트 케이스

1
2
assertEquals(5, test.solution(new String[][] {{"yellow_hat", "headgear"}, {"blue_sunglasses", "eyewear"}, {"green_turban", "headgear"}}));
assertEquals(3, test.solution(new String[][] {{"crow_mask", "face"}, {"blue_sunglasses", "face"}, {"green_turban", "face"}}));

참고 사이트