[프로그래머스] 72411번 - 메뉴 리뉴얼 (구현, 2021 KAKAO BLIND RECRUITMENT)

1. 문제 및 예제

 

 programmers에서 단계별로 문제를 풀다가 만난 문제다. 처음 문제를 보고 이게 대체... DP인가... 백트레킹인가... 싶었는데 입력 크기를 보고 무조건 브루트포스구나 싶었다. O(N^2)의 조합 문제로 해결하였다. 중간에 set container가 말을 안 들어서 vector로 전환하는 과정에서 시간이 좀 걸렸다. 30분에서 40분 정도? 걸린 것 같다.

---

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

프로그래머스

---

2. 풀이과정

 

 사실 해당 문제가 조금 까다로웠던 것은, 예제3번이다. 입력은 다음과 같다.

 

["XYZ", "XWY", "WXA"]

 

 이런 입력에서 "WX"가 두번으로 카운트되어야 한다. 그래서 나는 그냥 모든 입력을 정렬해줬다. 그럼 입력이 다음과 같이 바뀐다.

 

["XYZ", "WXY", "AWX"]

 

 하고 모든 문자열로 이루어질 수 있는 조합을 찾고 같은 것이 몇개인지 count하는 식으로 풀었다. 이 문제 역시 재귀함수로 해결하였다. 아무리 생각해도 조합은 재귀함수 만큼 좋은게 없는 것 같다. 첫 문제 나눔은 다음과 같이 하였다.

 

1. 모든 order 정렬

2. 뽑아야 하는 주문 갯수 별로 반복

3. 주문 갯수 별 나올 수 있는 조합을 vector에 등장 횟수와 함께 pair를 활용해 저장

4. 최댓값 찾기

 

 3의과정에서 괜히 시간 줄여보겠다고 set을 사용했는데, 그렇게 되면 find를 사용할 때 등장 횟수 까지 알아야 정확한 검색이 되길래 의미가 없어 vector로 O(N)의 탐색으로 구현하였다. 다음은 조합을 구하는 재귀함수이다.

 

void get_course_menu(int count, string order, int target_num, int start_num) {
    if (count < target_num) {
        for (int i = start_num; i < order.size(); i++) {
            if (!menus_index[i]) {
                menus_index[i] = true;
                get_course_menu(count + 1, order, target_num, i + 1);
                menus_index[i] = false;
            }
        }
    }
    else {
        string tmp = "";
        bool dir = false;
        for (int i = 0; i < order.size(); i++) {
            if (menus_index[i]) {
                tmp += order[i];
            }
        }

        for (int i = 0; i < ans.size(); i++) {
            if (ans[i].first == tmp) {
                ans[i].second = ans[i].second + 1;
                dir = true;
                break;
            }
        }

        if (!dir) {
            ans.push_back(make_pair(tmp, 1));
        }
    }
}

 

 처음에는 너무 무식하게 짠 것 같아서 조금 다듬은 코드이다. 정답 코드는 아래와 같다.

 

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

using namespace std;

bool visited[15];
bool menus_index[10];
vector<pair<string, int>> ans;

void get_course_menu(int count, string order, int target_num, int start_num) {
    if (count < target_num) {
        for (int i = start_num; i < order.size(); i++) {
            if (!menus_index[i]) {
                menus_index[i] = true;
                get_course_menu(count + 1, order, target_num, i + 1);
                menus_index[i] = false;
            }
        }
    }
    else {
        string tmp = "";
        bool dir = false;
        for (int i = 0; i < order.size(); i++) {
            if (menus_index[i]) {
                tmp += order[i];
            }
        }

        for (int i = 0; i < ans.size(); i++) {
            if (ans[i].first == tmp) {
                ans[i].second = ans[i].second + 1;
                dir = true;
                break;
            }
        }

        if (!dir) {
            ans.push_back(make_pair(tmp, 1));
        }
    }
}

vector<string> solution(vector<string> orders, vector<int> course) {
    
    vector<string> answer;

    for (int i = 0; i < orders.size(); i++) {
        sort(orders[i].begin(), orders[i].end());
    }

    for (auto menu_num : course) {
        int max = 0;
        vector<string> course_ans;
        ans.clear();

        for (auto it : orders) {
            for (int i = 0; i < 15; i++) {
                visited[i] = false;
            }
            get_course_menu(0, it, menu_num, 0);
        }

        for (auto it : ans) {

            cout << '(' << it.first << ' ' << it.second << ')';
        }
        cout << endl;

        for (auto it : ans) {
            if (it.second > max)
                max = it.second;
        }

        if (max > 1) {
            for (auto it : ans) {
                if (it.second == max) {
                    answer.push_back(it.first);
                }

            }

        }
    }

    sort(answer.begin(), answer.end());

    return answer;
}

 

3. 결어

 

 나름 원큐에 정답이 나와서 뿌듯했던 문제이다. 카카오 공식 레퍼런스에는 정답률이 25.40%라고 되어있던데 제출 횟수 기준 정답률인지 참석자 기준 정답률인지 알고싶다. programmers에서는 정답률이 48%라고 되어있는데 두 사이트에서 제공하는 정답률이 너무 차이가나서 한번 찾아보고싶다.