[프로그래머스] (Swift) Kakao - 메뉴 리뉴얼

문제 링크

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

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

 

문제 설명

• 입출력[예]는 아래와 같다 
• orders
  • orders에 사람들이 주문한 주문내역이 들어있다. 입출력 예시 1번으로 보면 6명의 사람들이 주문했다.
  • 첫번째 사람은 "ABCFG" 메뉴를 주문했다. A메뉴, B메뉴,,,,
• course
  • 주인공 '스카피'는 코스메뉴를 구성중이다.
  • [2, 3, 4] 라는 의미는, 2가지 메뉴로 구성된 코스, 3가지 메뉴로 구성된 코스,,, 이렇게 만들겠다는 뜻이다.
  • 코스요리를 구성할 수 있는 조건도 있다.
    • 코스요리는 최소 2명 이상의 손님으로 부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 넣을 수 있다.
    • 이 설명은 바로 아래 있는 사진을 보면 이해가 될 것이다.

• result
  • 주인공 '스카피'가 구성하게될 메뉴의 구성을 return 하기 위한 배열이다.
  • 오름차순으로 리턴해야한다.

 

내가 푼 풀이 (참고한 풀이 🥲)

• dfs 먼저 만들자
• 내가 만드려고 하는 course 의최대 길이보다, string(메뉴굿겅)이 길어질 경우에는 고려하지 않는다.

func dfs(index: Int, origin: [Character], newString: String) {
	// 구하려는 코스 길이보다, string(새로운 메뉴 구성)이 더 길다면 고려하지 않음
    if course.last! < newString.count{
        return
    }
	
    // string(새로운 메뉴 구성)이 set(메뉴개수: 등장횟수)에 존재하는지 확인
    // 존재한다면 += 1
    // 존재하지 않다면 메뉴 자체를 set 에 추가해줌
    if course.contains(newString.count) {
        if set.keys.contains(newString) {
            set[newString]! += 1
        } else {
            set[newString] = 1
        }
    }

	// dfs index 0부터 돌려서 재귀로 찾을 것
    for i in index..<origin.count {
        let c = origin[i]
        dfs(index: i+1, origin:  origin, newString: "\(newString)\(c)")
    }
}

 

• dfs 탐색 시작
• orders 로부터 주문을 하나씩 꺼내서 sorted로 정리해주고, 각각 dfs돌려주면서 음식 조합을 만들어준다

for order in orders {
    let order = order.sorted()
    dfs(index: 0, origin: order, newString: "")
    // print("order = \(order), set = \(set)")
    // print("----------------------")
}

이렇게 하게 되면,  아래 사진처럼 해당 order 에서 나올 수 있는 모든 메뉴구성이 등장

 

• 이제 위 메뉴 구성(set)에서 , 2번 이상 선택받은 메뉴만 선정해준다.
• 최댓값이 같으면 모두 포함해야한다! (4번등장한 메뉴가 "AB", "CD" 이면 둘다 포함해야한다는 뜻)

var result = [String]()
    
for length in course {
    let temp = set.filter { $0.key.count == length && $0.value > 1 }
    let maxNum = temp.max { $0.value < $1.value }
    let menu = temp.filter { maxNum!.value == $0.value }.map { $0.key }
    result.append(contentsOf: menu)
}

// return result.sorted() -> 최종적으로 sorted된 값을 return

 

 

최종 코드

import Foundation

//result = ["AC", "ACDE", "BCFG", "CDE"]
var orders = ["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"]
var course = [2,3,4]

func solution(_ orders:[String], _ course:[Int]) -> [String] {
    var set = [String: Int]()
    
    func dfs(index: Int, origin: [Character], newString: String) {
        if course.last! < newString.count{
            return
        }
        
        if course.contains(newString.count) {
            if set.keys.contains(newString) {
                set[newString]! += 1
            } else {
                set[newString] = 1
            }
        }
        
        for i in index..<origin.count {
            let c = origin[i]
            dfs(index: i+1, origin:  origin, newString: "\(newString)\(c)")
        }
    }
    
    // 탐색시작
    for order in orders {
        let order = order.sorted()
        dfs(index: 0, origin: order, newString: "")
//        print("order = \(order), set = \(set)")
//        print("----------------------")
    }
    // 조합중 2번이상 선택받은 메뉴만 가능
    // 최대값이 같으면 모두포함
    var result = [String]()
    
    for length in course {
        let temp = set.filter { $0.key.count == length && $0.value > 1 }
        let maxNum = temp.max { $0.value < $1.value }
        let menu = temp.filter { maxNum!.value == $0.value }.map { $0.key }
        result.append(contentsOf: menu)
    }
    return result.sorted()
    
}

print(solution(orders, course))