프로그래머스: 메뉴 리뉴얼 (Kotlin)

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

코딩테스트 연습 - 메뉴 리뉴얼

프로세스

1. orders의 각 문자열을 오름차순으로 정렬해서 저장한다.
2. orders의 원소마다 즉, 각 주문마다 course에서 주어진 코스 요리의 단품 메뉴 개수별 모든 조합을 구한다. 문자열을 (오름차순으로 정렬해놨기 때문에 앞에서부터 조합을 구성하면 자연스럽게 오름차순이 된다.)
3. 각 조합을 문자열로 변환해서 Map에 count한다.
4. 길이 별로 count 값이 가장 큰 조합을 모두 리스트에 추가한다.
5. 리스트를 오름차순 정렬해서 반환한다. 

풀이

카카오 2021 공채에 2번으로 나왔던 문제로 프로그래머스에서 난이도가 2로 되어 있지만, 코테 정답률은 25%로 많은 사람들이 어려워 했다. 삼성 A형 처럼 약간의 단계를 거치며 풀어야 하기 때문에, 조합 구하는 방법과 Map 조작에 익숙하지 않다면 풀다가 멘탈이 터질 수 있다.

 

풀이를 요약해보면 어렵진 않다. 각 주문마다 course 원소에 해당하는 길이마다 조합을 구해서 빈도 수를 count한다. 그리고 제일 많이 count된 조합을 모두 구한다.

 

근데 막상 풀려고 하면 부담이 된다. "아니 조합을 길이 별로 구해야 돼?" 조합에 자신이 없는 상태에서 만나면 이렇게 무식하게 푸는 게 맞는 건지 의구심이 들 수도 있다. 그런데 그렇게 푸는 거 맞다(ㅡ_ㅡ)

 

그리고 길이 별로 조합을 따로 저장한다. 단품 개수별로 가장 많이 나온 조합을 찾아야 하기 때문이다. 길이가 최대 10이므로 배열로 길이를 구분하고, 그 안에 Map을 저장할 수 있다.

 

마지막으로 길이별 Map을 value(빈도 수) 내림차순으로 정렬해서 첫 번째 원소의 빈도 수와 같은 key(조합)를 모두 리스트에 저장한다. 그리고 리스트를 정렬하면 정답을 구할... 수도 있고 틀릴 수도 있다. (1) 빈도 수가 2 이상인 조합만 구해야 하고, (2) 각 조합도 오름차순으로 정렬되어야 하기 때문이다.

 

따라서, 다 구하고 나서 각 조합(원소)을 정렬하거나, 처음에 order의 각 값을 오름차순으로 정렬을 해놓고 조합을 구할 때 왼쪽에서부터 순서대로 선택을 해서 자연스럽게 오름차순으로 만들 수도 있다. 

정리

(1) 각 주문을 오름차순으로 정렬한다.

private val mOrders = mutableListOf<CharArray>()
//...
for (order in orders) {
	mOrders.add(order.toCharArray().sortedArray())
}

(2) 개수 별로 조합의 빈도 수를 count할 배열과 Map을 준비한다.

// 조합을 저장할 배열 - combs[단품 개수][Map<조합, 빈도 수>]
private val combs: Array<MutableMap<String, Int>> = Array(11){ HashMap() }

(3) 주문마다 단품 메뉴 개수(길이) 별로 조합을 구한다.

for (order in mOrders) {
    for (combSize in course) {
        findComb(0, CharArray(combSize), order, 0) // 주문마다 필요한 길이 별 조합을 구한다
    }
}

//...

// combCount: 지금까지 선택한 메뉴의 개수, currentComb: 선택한 메뉴 저장하는 배열
// order: 주문(선택할 메뉴 후보들), startIdx: 선택 가능한 메뉴 범위의 시작 - startIdx ~ order.lastIndex
private fun findComb(combCount: Int, currentComb: CharArray, order: CharArray, startIdx: Int) {
    if (combCount >= currentComb.size) { // 다 뽑았으면,
        // 조합을 문자열로 변환
        val combination = StringBuilder().append(currentComb).toString() 
        
        if (combs[currentComb.size].contains(combination).not()) {
            combs[currentComb.size][combination] = 0
        }
        
        combs[currentComb.size][combination] = combs[currentComb.size][combination]!! + 1
        return
    }

    // 남아있는 메뉴 개수 < 앞으로 더 뽑아야할 메뉴 개수
    if (order.size - startIdx < currentComb.size - combCount) return

    // order[startIdx ~ order.lastIndex]에서 하나를 선택한다
    for (i in startIdx until order.size) {
        currentComb[combCount] = order[i]
        findComb(combCount + 1, currentComb, order, i + 1)
    }
}

(4) 길이 별로 가장 많이 나온 조합을 저장한다.

for (size in course) {
    if (combs[size].isEmpty()) continue // 해당 길이의 조합이 없을 수도 있다

    // map을 리스트로 바꾸면 Pair<key, value> 형태가 된다
    // value 기준 내림차순으로 정렬
    val combList = combs[size].toList().sortedByDescending { it.second }
    val maxCount = combList[0].second
    if (maxCount <= 1) continue // 2개 이상 나온 조합이어야 함

    // 가장 긴 조합들을 저장한다
    for (order in combList) {
        if (maxCount > order.second) break
        answer.add(order.first)
    }
}

전체 코드

import java.util.*

class Solution {
    // 조합을 저장할 배열 - combs[단품 개수][Map<조합, 빈도 수>]
    private val combs: Array<MutableMap<String, Int>> = Array(11){ HashMap() }
    private val mOrders = mutableListOf<CharArray>() // 주문 마다 오름차순의 CharArray로 바꿔서 저장한다

    fun solution(orders: Array<String>, course: IntArray): Array<String> {
        val answer = mutableListOf<String>()

        for (order in orders) {
            mOrders.add(order.toCharArray().sortedArray())
        }

        for (order in mOrders) {
            for (combSize in course) {
                findComb(0, CharArray(combSize), order, 0) // 주문마다 필요한 길이 별 조합을 구한다
            }
        }

        for (size in course) {
            if (combs[size].isEmpty()) continue // 해당 길이의 조합이 없을 수도 있다

            // map을 리스트로 바꾸면 Pair<key, value> 형태가 된다
            // value 기준 내림차순으로 정렬
            val combList = combs[size].toList().sortedByDescending { it.second }
            val maxCount = combList[0].second
            if (maxCount <= 1) continue // 2개 이상 나온 조합이어야 함
            
            // 가장 긴 조합들을 저장한다
            for (order in combList) {
                if (maxCount > order.second) break
                answer.add(order.first)
            }
        }

        return answer.sorted().toTypedArray()
    }

    // combCount: 지금까지 선택한 메뉴의 개수, currentComb: 선택한 메뉴 저장하는 배열
    // order: 주문(선택할 메뉴 후보들), startIdx: 선택 가능한 메뉴 범위 - startIdx ~ order.lastIndex
    private fun findComb(combCount: Int, currentComb: CharArray, order: CharArray, startIdx: Int) {
        if (combCount >= currentComb.size) { // 다 뽑았으면,
            // 조합을 문자열로 변환
            val combination = StringBuilder().append(currentComb).toString()
            
            if (combs[currentComb.size].contains(combination).not()) {
                combs[currentComb.size][combination] = 0
            }
            
            combs[currentComb.size][combination] = combs[currentComb.size][combination]!! + 1
            return
        }

        // 남아있는 메뉴 개수 < 앞으로 더 뽑아야할 메뉴 개수
        if (order.size - startIdx < currentComb.size - combCount) return

        for (i in startIdx until order.size) {
            currentComb[combCount] = order[i]
            findComb(combCount + 1, currentComb, order, i + 1)
        }
    }
}

회고

알고리즘이나 아이디어가 어려운 문제는 아니었는데, 조합이나 Map을 다루는 것이 능숙하지 않아서 어렵게 느꼈던 것 같다. 조합 구하는 거 자신 있다고 생각했었는데 착각이었다..ㅋㅋ. 복잡한 문자열 관련 문제들 중 대부분이 조합과 Map을 사용하는 것 같아서 이번 기회에 정리하고 넘어간다.