Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[Algorithm] 메뉴 리뉴얼 #19

Closed
hwangJi-dev opened this issue Sep 23, 2022 · 0 comments
Closed

[Algorithm] 메뉴 리뉴얼 #19

hwangJi-dev opened this issue Sep 23, 2022 · 0 comments

Comments

@hwangJi-dev
Copy link
Owner

hwangJi-dev commented Sep 23, 2022

💬 문제

[문제]

각 손님들이 주문한 단품메뉴들이 문자열 형식으로 담긴 배열 orders, "스카피"가 추가하고 싶어하는 코스요리를 구성하는 단품메뉴들의 갯수가 담긴 배열 course가 매개변수로 주어질 때, "스카피"가 새로 추가하게 될 코스요리의 메뉴 구성을 문자열 형태로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.


💬 Idea

  • 처음에 1번 입출력 예시만 보고 이거구나! 하며 문제 풀이를 시작한 탓에 다른 테케들을 맞추지 못했다.
    • 문제를 잘못 이해했다.
  • 메뉴 개수에 대한 조합을 미리 만들어 놓고, 개수별 조합 중 가장 많이 주문된 조합 을 return하는 것이 핵심이었다.
    • 개수별로 가장 많이 주문된 조합이 여러개일 수도 있다는 점에 유의하자 (최고 주문 횟수가 같을 경우)
    • 처음에 지문을 읽어봐도 힌트를 얻기 쉽지 않아서 이 부분에 대해 긴가민가 했다,, 아직도 이해가 잘 가지 않는다.. ^^..

💬 풀이

[잘못 이해하고 푼 풀이!!]

func solution(_ orders:[String], _ course:[Int]) -> [String] {
    var candidateMenu: [String] = []
    
    // 후보가 될 메뉴 조합(코스)을 뽑는다
    for order in orders {
        for course in course {
            if course == order.count {
                candidateMenu.append(order)
            }
        }
    }
    
    // 각 코스요리 메뉴의 구성을 문자열 형식으로 배열에 담아
    // 사전 순으로 오름차순 정렬
    return check(orders, course, Set(candidateMenu).map{ String($0) }).sorted()
}

func check(_ orders: [String], _ course: [Int], _ menu: [String]) -> [String] {
    var menuArray: [String] = []
    
    for menu in menu {
        let menuElement = Array(menu).map{ String($0) }
        var sum = 0
        for order in orders {
            // contains로 중복 검사
            if order.count > menuElement.count {
                var elementCount = 0
                for element in menuElement {
                    if order.contains(element) {
                        elementCount += 1
                    }
                }
                
                if elementCount >= 2 {
                    sum += 1
                }
            } else if order.count == menuElement.count {
                if order == menu {
                    // 완전일치
                    sum += 1
                }
            }
        }
        
        // 주문한 횟수가 2번 이상이므로
        // 메뉴에 등극
        if sum >= 2 {
            menuArray.append(menu)
        }
    }
    
    return menuArray
}

solution(["ABCDE", "AB", "CD", "ADE", "XYZ", "XYZ", "ACD"], [2,3,5])

➡️ 테케 1번만 맞췄다. 무언가 잘못되었다고 느끼고 문제를 다시 보기 시작했다...


[제대로 된 풀이]

  • 메뉴별 조합을 만들어 Dictionary에 저장한 후 Count를 비교하여
  • 메뉴 개수별 최대 주문된 조합만을 result에 append해주었다.
import Foundation

var resultDict: [[String]: Int] = [:]

func solution(_ orders:[String], _ course:[Int]) -> [String] {
    
    for course in course {
        for order in orders {
            combination(Array(order.sorted()).map{ String($0) }, course)
        }
    }
    
    var result: [String] = []
    for course in course {
        // 최소 주문 횟수가 2 이상인 경우에 한해서만
        // 코스 등록이 가능하므로 maxCount를 2로 설정한다.
        var maxCount = 2
        var possibleMenu: [String] = []
        
        for menu in resultDict.keys {
            if menu.count == course {
                if resultDict[menu]! > maxCount {
                    maxCount = resultDict[menu]!
                    possibleMenu = [menu.sorted().joined()]
                } else if resultDict[menu] == maxCount {
                    possibleMenu.append(menu.sorted().joined())
                }
            }
        }
        
        possibleMenu.forEach {
            result.append($0)
        }
    }
    
    return result.sorted()
}

// MARK: - 조합
func combination(_ array: [String], _ n: Int) {
    if array.count < n { return }

    func cycle(_ index: Int, _ now: [String]) {
        if now.count == n {
            resultDict[now] = resultDict[now] != nil ? resultDict[now]! + 1 : 1
            return
        }

        for i in index..<array.count {
            cycle(i + 1, now + [array[i]])
        }
    }

    cycle(0,[])
}

💬 알게된 점

  • 문제를 꼼꼼히 읽고, 입출력 예시를 통해 문제에서 요구하는 바를 정확하게 이해하자!!!..

  • Swift에서 ‘조합’ 사용하기

    func combination<T: Comparable>(_ array: [T], _ n: Int) -> [[T]] {
        var result = [[T]]()
        if array.count < n { return result }
    
        func cycle(_ index: Int, _ now: [T]) {
            if now.count == n {
                result.append(now)
                return
            }
    
            for i in index..<array.count {
                cycle(i + 1, now + [array[i]])
            }
        }
    
        cycle(0,[])
    
        return result
    }
  • Swift에서 ‘순열’ 사용하기

    func permutation<T: Comparable>(_ array: [T], _ n: Int) -> [[T]] {
        var result = [[T]]()
        if array.count < n { return result }
    
        var visited = Array(repeating: false, count: array.count)
    
        func cycle(_ now: [T]) {
            if now.count == n {
                result.append(now)
                return
            }
    
            for i in 0..<array.count {
                if visited[i] {
                    continue
                } else {
                    visited[i] = true
                    cycle(now + [array[i]])
                    visited[i] = false
                }
            }
        }
    
        cycle([])
    
        return result
    }
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant