티스토리 뷰

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

 

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

레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서

programmers.co.kr

2021 KAKAO BLIND RECRUITMENT : 메뉴 리뉴얼

손님이 주문한 단품메뉴의 목록이 아래와 같이 score 배열로 주어지고

1번 손님 A, B, C, F, G
2번 손님 A, C
3번 손님 C, D, E
4번 손님 A, C, D, E
5번 손님 B, C, F, G
6번 손님 A, C, D, E, H

이 중 두 개 이상의 메뉴를 조합하여 코스요리를 구성하려고 한다.

코스요리는 해당 조합으로 두 명 이상의 손님에게 주문된 이력이 있어야한다. 

후보 코스 요리 중 가장 많은 손님이 주문했던 코스 요리들이 최종 결과가 된다. (주문된 빈도수가 같은 경우 모두 최종 결과에 포함한다)

주문 이력과 함께 코스요리를 구성하는 메뉴의 갯수가 담긴 배열도 함께 전달된다.

해당 갯수 만큼의 메뉴를 포함하는 코스요리를 구성해야하는 것

orders course result
["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"] [2,3,4] ["AC", "ACDE", "BCFG", "CDE"]
["ABCDE", "AB", "CD", "ADE", "XYZ", "XYZ", "ACD"] [2,3,5] ["ACD", "AD", "ADE", "CD", "XYZ"]
["XYZ", "XWY", "WXA"] [2,3,4] ["WX", "XY"]

접근방법

우선 구성해야하는 코스요리의 메뉴 수 하나 마다 하나의 반복문을 돈다. (course 배열의 반복문을 돈다는 뜻)

  예를 들어 2개의 메뉴로 구성된 코스요리를 만들어야하는 반복문에 들어왔다면

  모든 손님의 주문 이력을 탐색한다. (orders 배열의 반복문)

  주문 이력 하나는 한 손님이 주문한 단품 메뉴의 목록이다. 이 단품메뉴들로 구성할 수 있는 2개의 코스요리 경우를 모두 구한다. (next_permutation 사용하여 조합구하는 방법 사용)

  map을 사용하여 해당 메뉴 조합의 빈도수를 갱신한다. (+1)

  이렇게 모든 손님의 주문 이력을 탐색하여 2개로 구성할 수 있는 모든 메뉴 조합의 빈도수를 map에 저장했다면 map에서 가장 빈도수가 높은 메뉴 조합을 최종 결과인 answer에 담는다. 

이렇게 모든 course에 대해 반복한다. (다음은 3개로 구성된 코스요리)

이 때 주의할 점은 메뉴 조합을 구성했을 때 문자열을 정렬해줘야한다. 그래야 문자열 배열은 다르지만 같은 메뉴들로 구성된 조합이 같은 메뉴 조합으로 인식될 수 있다. (e.g. ABC, BCA -> 모두 ABC로 인식되어야함)

그리고 내가 푼 방식의 경우 구성해야할 단품메뉴의 수가 한 손님이 주문한 단품메뉴의 수보다 클 경우를 따로 처리해줘야 했다.
* 3개를 주문한 손님에게서 4개의 단품 메뉴로 구성된 코스요리 조합은 구할 수 없다.

나의 경우 빈도수를 갱신할 때 최대 빈도수도 같이 갱신해줬다. 마지막에 최대 빈도수를 가진 메뉴조합을 결과에 담아야할 때 map에서 최대 빈도수를 가진 메뉴조합들만 찾았다. + 이때 최대 빈도수 값을 2로 초기화하여 2명 이상의 손님에게 주문된 메뉴조합만 담을 수 있게 했다.

map의 for문을 돌 때 auto를 사용하는 것이 대부분이지만 map이 pair를 사용하기 때문에 pair로 담아도 된다. auto로 담아도 똑같다. 그래도 이왕이면 알고 있는 자료형에 대해서는 auto를 쓰는 것 보다 명시해주는 것이 더 효율적이다.

그리고 마지막에 answer (최종 결과) 를 알파벳 오름차순으로 정렬해주는 것도 잊지 말아야 한다.

소스코드

#include <string>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    
    for(int numOfMenu : course){
        map<string, int> crsFreq;
        int maxFreq = 2;
        
        for(string order : orders){
            
            long n = order.length();
            int k = numOfMenu;
            if(n < k) continue;
            
            vector<int> combi(n-k, 0);
            for(int i = 0 ; i < k ; i++)
                combi.push_back(1);
            
            do {
                string setMenu;
                for(int i = 0 ; i < n ; i++){
                    if(combi[i] == 1)
                        setMenu += order[i];
                }
                sort(setMenu.begin(), setMenu.end());
                crsFreq[setMenu] += 1;
                maxFreq = max(crsFreq[setMenu], maxFreq);
            } while (next_permutation(combi.begin(), combi.end()));
        }
        
        for (pair<string, int> crs : crsFreq){
            if (crs.second == maxFreq)
                answer.push_back(crs.first);
        }
        sort(answer.begin(), answer.end());
    }
    return answer;
}
댓글
댓글쓰기 폼