99 클럽 코딩 테스트 스터디 미들러 6일차 - 의상

https://school.programmers.co.kr/learn/courses/30/lessons/42578?language=java

프로그래머스

 

[문제]

코니는 매일 다른 옷을 조합하여 입는 것을 좋아합니다.

예를 들어 코니가 가진 옷이 아래와 같고, 오늘 코니가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.

종류	이름
얼굴	동그란 안경, 검정 선글라스
상의	파란색 티셔츠
하의	청바지
겉옷	긴 코트

코니는 각 종류별로 최대 1가지 의상만 착용할 수 있습니다. 예를 들어 위 예시의 경우 동그란 안경과 검정 선글라스를 동시에 착용할 수는 없습니다.

• 착용한 의상의 일부가 겹치더라도, 다른 의상이 겹치지 않거나, 혹은 의상을 추가로 더 착용한 경우에는 서로 다른 방법으로 옷을 착용한 것으로 계산합니다.
• 코니는 하루에 최소 한 개의 의상은 입습니다.

코니가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

 

[제한 사항]

• clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
• 코니가 가진 의상의 수는 1개 이상 30개 이하입니다.
• 같은 이름을 가진 의상은 존재하지 않습니다.
• clothes의 모든 원소는 문자열로 이루어져 있습니다.
• 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.

[입출력 예]

 

[풀이]

직관적으로 경우의 수를 생각해서 정리를 해보자면 1번 예시의 경우에는

1. yellow_hat
2. blue_sunglasses
3. green_turban
4. yellow_hat + blue_sunglasses
5. green_turban + blue_sunglasses

이렇게 5가지 경우가 존재하는 것을 알 수 있습니다.

 

2번 예시의 경우에는 전부 같은 타입이니 각각 1개씩 입는 3가지의 경우만 존재하는 것을 알 수 있습니다.

이제 여기서 경우의 수를 구하기 위한 계산식을 추출해 보겠습니다.

 

1번 예시를 기준으로 아이템 종류: 해당하는 아이템 개수로 묶어서 Map처럼 생각을 해본다면

headgear	2
eyewear	1

위처럼 정리할 수 있습니다.

여기서 각 종류별로 케이스를 세어보면 headgear는 첫 번째 기어 착용, 두 번째 기어 착용, 아예 착용 안 함 -> 총 3가지 경우의 수가 나오게 됩니다. eyewear는 1개 있는 것 착용, 아예 착용 안함 -> 총 2가지 경우의 수가 있습니다.

경우의 수를 구하는 공식은 타입별로 가능한 케이스끼리 곱해주면 됩니다. 즉 모든 경우의 수는 3 x 2 = 6가지가 존재합니다.

위에서 직관적으로 생각했을 때와는 1가지 경우가 다르죠. 아무것도 착용하지 않은 경우가 있기 때문입니다.

문제에서 코나는 최소한 1개의 의상은 입어야 하므로 해당 1가지 경우의 수는 빼줘야 합니다. 그래서 5가지로 계산이 됩니다.

 

이제 해당 문제를 먼저 자바 코드로 구현해 보겠습니다.

import java.util.HashMap;
import java.util.Iterator;

class Solution {
    public int solution(String[][] clothes) {
        HashMap<String, Integer> map = new HashMap<>();
        for (String[] item : clothes) {
            String type = item[1];
            map.put(type, map.getOrDefault(type, 0) + 1);
        }

        Iterator<Integer> it = map.values().iterator();
        int answer = 1;

        while (it.hasNext()) {
            answer *= it.next() + 1;
        }
        
        return answer - 1;
    }
}

HashMap을 활용하여 아이템 종류를 key 값으로, 주어진 리스트에서 나오는 해당 종류의 횟수를 value로 지정했습니다.

이제 해당 map의 values를 반복문을 돌면서 케이스 값을 더해줍니다. 그리고 마지막에는 아무것도 입지 않는 경우 1개를 빼주는 방식으로 구현 가능했습니다.

(getOrDefault 함수는 Map에서 특정 값을 추출할 때, 해당 값이 존재하지 않는다면 대체할 기본 값을 정의해서 가져오는 함수입니다.)

 

이번엔 코틀린으로 구현한 내용입니다.

class Solution {
    fun solution(clothes: Array<Array<String>>): Int {
        val arr = mutableMapOf<String, Int>()

        clothes.forEach {
            arr[it[1]] = (arr[it[1]] ?: 1) + 1
        }
        return arr.values.fold(1) { acc, i ->
            acc * i
        } - 1
    }
}

똑같이 Map을 선언하여 특정 종류별로 존재 횟수를 계산해 줍니다.

이번엔 fold() 함수를 사용했습니다.

fold 함수는 컬렉션을 반복하면서 초기값과 컬렉션의 각 요소를 조합해 하나의 값을 반환하는 함수입니다.

이 함수는 누적 연산을 수행할 때 유용합니다.

fold() 함수의 내용을 보자면

public inline fun <T, R> Iterable<T>.fold(initial: R, operation: (acc: R, T) -> R): R {
    var accumulator = initial
    for (element in this) accumulator = operation(accumulator, element)
    return accumulator
}

초기 값을 기반으로 각 element를 통해 핸들러로 처리받는 특정 연산을 수행할 수 있도록 구성된 것을 확인하실 수 있습니다.

이를 통해 경우의 수를 축적 계산하고 마지막에 어떤 것도 입지 않는 경우의 수 1가지를 빼주면 되겠습니다.