<프로그래머스> 메뉴 리뉴얼(Lv.2)
[깃허브]
[프로그래머스]
https://school.programmers.co.kr/learn/courses/30/lessons/72411
진짜 문제 길다... 길어... 점점 익숙해져간다.
처음에 이렇게 긴 문제를 보면 심장이 막 뛰고 그랬는데 이제는 차분하게 읽기 시작한다.
이번에도 카카오에서 나왔던 문제였다.
조건에 맞는 코스메뉴 후보들을 뽑아내는 문제였는데 쉽지 않겠다는 생각이 들었고 그 생각을 문제 푸는 처음 1시간동안 했다.
그 말은... 진행을 못했다는 거다.
어디서부터 손을 대야하고 어떻게 만져야할지 감이 안 오더라
그래도 어디까지 했었냐면 메뉴 개수에 따라 그룹핑 하는 것과... 여기까지였다.
진짜 막막했다.
잠시 다른 것을 하고 다시 돌아와서 집중 모드에 들어가고 나서부터는 조금씩 진행이 되었다.
단품 메뉴들을 뽑아야하니까 먼저 순열이 생각났다.
그런데 짜고 나니까 순서와는 상관없어야 한다는게 번뜩 떠올라서 조합으로 변경했다.
그래도 순열을 구현할 때 새롭게 코드를 알게 됐다.
바로 제너릭 타입과 flatMap을 사용하는 방법이다.
private fun<T> permutation(depth: Int, sub: List<T>, add: List<T> = listOf()): List<List<T>> {
return if (add.size == depth) {
listOf(add)
} else {
sub.flatMap { permutation(depth, sub - it, add + it) }
}
}
// 출처 : https://notepad96.tistory.com/108아직 제대로 이해하지는 못했지만 필요할 때마다 여기서 가져가야지~(감사할 따름)
조합은 이미 익숙한 방식으로 구현했다.
그럼 이제 해야하는 건 어떻게 가장 많은 사람들이 뽑은 메뉴 조합을 찾아낼 것인가였다.
나 약간 2중 반복문에 대해 거부감이 있는 거 같다.
'써야하나...?' 생각이 들 때마다 바로 딴 방법만 주구장창 찾는다.
그래도 오늘은 문제 보면 상당히 크기 제한이 작아서 충분히 통과하겠다라는 생각이 들었기에 2중 반복문을 사용했다.
이제 전체적인 구조도 어느정도 나왔고 조합 함수 안에서 큰 값 뽑는 처리를 해볼까 했는데 너무 코드가 더러워졌다.
길기도 엄청 길어지고...
그래서 고민을 하다가 Map이 떠올랐다.
각 사람이 그 메뉴 조합이 있는지 확인하고 값만 넣으면 되니까 충분히 가능한 선택지라고 생각했다.
그래서 StringBuilder로 메뉴 조합을 저장해놨다가 Map에 집어넣었다.
그리고 거기에서 가장 큰 value를 가진 key값을 answer에 저장했다.
모든 길이를 한번에 하려니까 잘 안돼서 2개의 메뉴 조합끼리, 3개의 메뉴 조합끼리 나눠서 진행했고 value값이 동일하다면 다 answer에 넣어야했기에 value의 최댓값을 구한다음 반복문을 통해서 key를 가져왔다.
마지막으로는 answer가 사전순으로 정렬되어야 했기 때문에 정렬까지 했다.
그리고 예제를 돌려보는데 안 되는 케이스들이 있더라
그건 예외처리를 안 했기 때문이었는데 메뉴를 선택한 사람이 2명이상인지를 제대로 체크하지 않았었다.
그래서 그 부분을 막고 나서 다시 돌려보는데 또 안 되는 케이스들이 있더라
그건 XW, WX 같이 순서가 다른 요소들을 다르게 처리했기 때문이었는데 이거는 StringBuilder로 받은 값을 먼저 정렬시켜줌으로써 해결했다.
그리고 제출했더니 통과였다..!!
해당 방법으로 작성한 코드는 다음과 같다.
class Solution {
// 코스 메뉴 후보
lateinit var candidate: MutableMap<String, Int>
fun solution(orders: Array<String>, course: IntArray): Array<String> {
// 결정된 코스 메뉴
var answer: Array<String> = arrayOf<String>()
// 메뉴 개수로 그룹핑
var check = orders.groupingBy { it.length }.eachCount()
for (c in course) {
// 예외처리 1
var sum = 0
check.forEach { (key, value) ->
if (key >= c) sum += value
}
if (sum < 2) continue
candidate = mutableMapOf()
for (order in orders) {
// 예외처리 2
if (order.length < c) continue
combination(c, 0, 0, order)
}
// 예외처리 3
val max = candidate.maxOf { it.value }
if (max < 2) continue
candidate.forEach { (key, value) ->
if (value == max) answer += key
}
}
return answer.sortedArray()
}
val picked = StringBuilder()
private fun combination(depth: Int, add: Int, start: Int, order: String) {
if (depth == add) {
// 받은 메뉴 정렬
val str = picked.split("").sorted().joinToString("")
if (candidate.containsKey(str)) {
candidate[str] = candidate[str]!! + 1
} else {
candidate[str] = 1
}
return
}
for (i in start until order.length) {
picked.append(order[i])
combination(depth, add + 1, i + 1, order)
picked.deleteCharAt(picked.lastIndex)
}
}
}
카카오 문제들은 푸는거에 만족하지말고 시간 단축을 목표로 해야겠다~!