프로그래머스 - 메뉴 리뉴얼

문제

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

프로그래머스

메뉴의 조합을 찾아 가장 많이 나온 메뉴를 찾아내는 문제였다.

 

문제 풀이

설마 이걸 완전탐색으로 풀어야하나..? 아니겠지..? → 완전탐색
아 그냥 완전탐색으로 풀면 안되나; → 완전탐색 아님

 

매번 sort하기 싫어서 order를 sort한 후 저장해서 넣었더니 테스트 케이스는 모두 맞는데 제출하고 채점하니 0점이 나왔다. 왜인지는 찾지 못했고, 그때그때 sort 하도록 변경했더니 100점이 나왔다. 왜그랬을까..?

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

using namespace std;

map<string, int> courseMap;
vector<string> answer;
bool compare(pair<string, int> a, pair<string, int> b){
    return a.second > b.second;
}

void dfs(string order, string course, int n, int index){
    if(course.length() == n){
        courseMap[course]++;
        return;
    }
    for(int i=index;i<order.length();i++){
        dfs(order, course+order[i], n, i+1);
    }
}

void findCourse(vector<string> orders, vector<int> courseNum){
    //각 주문별 조합 찾기
    for(int num:courseNum){
        for(string s:orders){
            sort(s.begin(), s.end());
            dfs(s, "", num, 0);
        }
        vector<pair<string, int>> courseList (courseMap.begin(), courseMap.end());
        sort(courseList.begin(), courseList.end(), compare);
        
        int maxCnt = courseList[0].second;
        for(pair<string, int> p:courseList){
            if(p.second < 2) break;
            if(p.second == maxCnt){
                answer.push_back(p.first);
            }
        }
        courseMap.clear();
    }
}

vector<string> solution(vector<string> orders, vector<int> course) {   
    //조합 찾기
    findCourse(orders, course);

    //answer 사전 순으로 오름차순 정렬
    sort(answer.begin(), answer.end());
    return answer;
}