[프로그래머스] 메뉴 리뉴얼

https://programmers.co.kr/learn/courses/30/lessons/72411?language=swift# 

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

 

2021 KAKAO BLIND RECRUITMENT의 문제로 25.40%의 정답률을 기록한 문제이다. 

 

첫 아이디어만 잘 생각하면 코드로 옮기는 것은 크게 문제가 없어보이는 문제.

요구되는 조건 및 제한사항들을 잘 살펴보는게 중요하다. 

 

우선 생각한 방법을 봐보자. 

 

1. orders의 원소 중 가장 긴 원소의 길이보다 큰 course에 대해서는 continue 처리한다.

   (왜냐? 난 길이가 5인데 6개를 고르는 경우는 말이 안되기 때문!)

2. course의 원소인 c를 기준으로 orders를 for문으로 돌며 조합을 구해야하는지 말아야 하는지 c를 기준으로 판단한다. 

  2-1. 판단 이전에 먼저 order를 오름차순 정렬하여 조합했을 때 순서가 바뀌는 일이 없도록 한다. 

         (조합 코드상으로는 순서가 바뀌는 값이 나오지는 않으나, 애초에 원배열을 넣을 때 반대로 들어가면 이런 경우가 발생하기 원배열을 정렬하는 것!)

  2-2. order.count > c 일 때는 조합을 구해줘야 한다. 

          내가 선택할 메뉴는 2개인데 실제 주문은 3개였다면 그 안에서 2개를 고르는 조합을 구할 수 있기 때문이다. 

  2-3. order.count == c 인 경우는 그 자체가 조합이기에, 그대로 저장해준다. 

  2-4. 2번을 계속 반복하며 딕셔너리에 등장 횟수를 기록해준다. 

3. 딕셔너리의 values를 기준으로 내림차순 해준다. 그 후 최댓값을 구하고

4. 정렬된 딕셔너리를 돌면서 value가 최댓값과 같고 1보다 크다면 (2명 이상에게 주문 받은 경우여야 하기 때문) 결과에 저장 

5. 결과를 오름차순 정렬하여 리턴

 

 

이렇겍 보면 조금 복잡해 보이나, 실제로 사용되는 개념은 "조합"이 거의 전부이다.

나머지는 조건에 맞게 등장횟수를 비교하고 문자열을 다루는 정도?이다. 

 

바로 코드로 봐보자!

 

import Foundation

func solution(_ orders:[String], _ course:[Int]) -> [String] {
    // orders 중 가장 긴 배열의 길이를 저장한다. 
    // 나중에 이 보다 큰 course가 오면 그냥 패스하기 위해
    let ordersMaxCount = orders.map {$0.count}.max()!
    // 결과 배열 저장 
    var result = [String]()   
    
    // course의 수로 돈다.
    for c in course {
        // 조합의 등장 횟수를 저장할 딕셔너리
        var dict = [String:Int]()
        
        // orders의 원소 중 가장 긴 것 보다 크면 성립 자체가 안됨
        if c > ordersMaxCount {
            continue
        }

        // orders를 돌면서 조합을 구해준다. 
        for order in orders {
            // 조합을 구하기 이전에 order를 정렬해준다. 
            // ACB ABC는 같은 것이기에 사전 조건을 통일해주는 것이다. (모두 오름차순 정렬)
            let orderSorted = order.map {String($0)}.sorted {$0 < $1}
            // c보다 길이가 크다면 c의 개수로 조합을 구해줘야 한다. 
            if orderSorted.count > c {
                let combs = combinations(orderSorted, c)
                // 키는 다시 문자열 형태로 합쳐서 저장
                let key = combs.map {$0.joined()}
                // 딕셔너리에 저장해준다.
                key.map {
                   dict[$0, default: 0] += 1 
                } 
            // c와 길이가 같다면 조합이 필요하지 않음. 즉 바로 저장
            } else if orderSorted.count == c {
                dict[orderSorted.joined(), default: 0] += 1
            }
        }
        
        // 딕셔너리의 value를 기준으로 내림차순 정렬해준다
        let sortedDict = dict.sorted {$0.1 > $1.1}
        // 가장 첫 원소의 value = max
        let maxVal = sortedDict.first!.1

        // 정렬된 dict를 돌면서 v가 maxVal과 같다면 key를 저장해준다. 
        // 그릭고 최소 두 명에게서 주문 받아야 하는 조건 충족을 위해 v > 1을 넣어준다. 
        for (k,v) in sortedDict {
            if v == maxVal && v > 1 {
                result.append(k)
            }
        }

    } 
    // 결과는 오름차순으로 정렬 
    return result.sorted {$0 < $1}
}


// 자주 사용하는 조합 코드 
func combinations<T>(_ elements: [T], _ k: Int) -> [[T]] {
    if elements.count == k {
        return [elements]
    }
    if k == 0 {
        return []
    } 
    if k == 1 {
        return elements.map { [$0] }
    }
    var result = [[T]]()
    let subarray = Array(elements.suffix(from: 1))

    let subcombos = combinations(subarray, k-1)
    result += subcombos.map { [elements[0]] + $0 }
    result += combinations(subarray, k)
    return result
}

 

조금 걸리긴 했으나, 그래도 오랜만에 수월하게 풀린 레벨2 문제였다. 

 

끄읕