메뉴 리뉴얼

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

프로그래머스

 

문제 설명은, 문제 사이트가 가장 잘 설명하기 때문에 생략합니다.

 

아이디어

 

가장 먼저, 완전 탐색을 고려했습니다.

모든 course에 대해 모든 orders를 탐색하면서 모든 조합을 구하는 경우수는 ... ?

course탐색 : 최대10

orders탐색: 최대20

하나의 order에 대한 조합 구하기: 길이 10의 string에서 course가 5일 때 최대 => 10C5 < 10^5

이렇게 제가 구한 시간복잡도는 10*20*10^5 이므로 O(10^7) 입니다. 

따라서, 다른 풀이를 고려하지 않고 완전 탐색으로 그대로 풀이를 진행했습니다.

 

 

코드

 

#include <string>
#include <vector>
#include <unordered_map>
#include <iostream>
#include <algorithm>

using namespace std;

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    
    // 완탐 고려
    // course가 2~10 일때 + order 개수가 20, 길이가 10일 때
    // (10C2 + 10C3 + ... + 10C10) * 20 => 최대 10C5 * 20 < 10^5
    
    // x개 선택 어떻게 할까? next_permutation onoff의 1 개수 조절
    // map 순회 어떻게 할까? 
    
    // 1. course 고정
    for (int courseIdx = 0; courseIdx < course.size(); courseIdx++) {
        unordered_map<string, int> um; // 모든 조합 + 등장횟수 저장
        int curCourse = course[courseIdx];
        
        int maxCombCount = 0;
        
        // 2. order 고정
        for (int orderIdx = 0; orderIdx < orders.size(); orderIdx++) {
            string curOrder = orders[orderIdx];
            int orderLength = curOrder.size();
            if (orderLength < curCourse) continue;
            vector<int> onOff;
            for (int i = 0; i < orderLength; i++) {
                if (i >= orderLength - curCourse) {
                    onOff.push_back(1);
                } else {
                    onOff.push_back(0);
                }
            }
            
            do {
                vector<char> combinationResult;
                for (int i = 0; i < orderLength; i++) {
                    if (onOff[i]) combinationResult.push_back(curOrder[i]);
                }
                sort(combinationResult.begin(), combinationResult.end());
                
                string tmpString = "";
                for (auto c: combinationResult) {
                    tmpString += c;
                }
                um[tmpString]++;
                maxCombCount = max(maxCombCount, um[tmpString]);
            } while (next_permutation(onOff.begin(), onOff.end()));
        }
        for (auto e: um) {
            if (maxCombCount < 2) break;
            if (e.second == maxCombCount) {
                answer.push_back(e.first);
            }
        }
    }
    
    sort(answer.begin(), answer.end());
    
    return answer;
}

 

초기 풀이입니다.

전부 탐색하는 과정에서 가장 중요한 것은 조합을 찾아내는 것입니다.

모든 조합을 구하기 위해서 next_permutation을 사용했으며, onOff라는 vector를 두어 course의 길이만큼 뒤에서부터 1로 설정했습니다.

 

 

실수한 점

 

큰 어려움 없이 문제를 해결했지만, 그 과정에서 여러 번의 실수가 있었습니다.

 

1) 메뉴 조합은 2번 이상 등장해야 한다는 문제의 조건을 깜빡했다.

2) onOff의 길이를 고정시켜놓고 거기에 push_back을 했다. (길이가 고정된 vector에 push를 하면 길이가 늘어납니다.)

3) map을 순회하는 방법을 까먹어서 테스트하느라 시간을 썼다.

 

 

다른 사람의 풀이를 보며 배운 점

 

다른 사람들도 저와 유사한 풀이를 했을 줄 알았는데, 오히려 dfs를 사용하시는 분이 많았습니다.

dfs..를 왜 쓰지..? 라는 생각이 들어서 조금 정리 해보려 합니다.

 

참고한 해설은 다음과 같습니다.

https://cherishvert.tistory.com/109

[프로그래머스] 메뉴 리뉴얼 C++ (Lv.2)

 

 

별표친 부분을 조금 더 자세하게 설명하면

 

 

파란색 화살표를 따라가면 쉽게 이해할 수 있을 겁니다.

이런식으로 길이 2의 조합을 모두 찾을 수 있습니다.

사실상 2중 for문을 쓰는 것이랑 비슷한데, 최대 10중for문까지 만들 수는 없으니까 n중for문을 dfs로 구현했다 라고 보는게 맞는 것 같습니다.

 

전 이런 조합을 구하는 문제면 항상 next_permutation을 애용하지만, 이런 방식도 꽤 괜찮은 것 같습니다.

 

그리고 뭐든 설명할 때 애니메이션으로 보여주면 이해가 쉽겠다 라는 생각이 들어서 다음에 시간이 된다면 애니메이션을 넣어보도록 하겠습니다!