[프로그래머스] 메뉴리뉴얼, C++

프로그래머스

문제 요약

손님들이 주문한 단품 메뉴로 코스요리(조합)를 만든다. 코스 요리는 단품 두개 이 상으로 이루어져있다.
코스 요리의 길이(단품 메뉴의 개수)를 보고 그 중에 가장 많이 선택된 조합을 반환한다.

 

접근

모든 손님들이 주문한 단품 메뉴로 모든 조합을 만들어야한다. 조합을 만들 때 반복문, 라이브러리, 백트래킹으로 구현할수 있다.

1. 조합만들기 - 반복문

반복문을 중첩해서 사용하면 쉽게 조합을 만들수 있다.
예를 들면 ABCDE에서 3개의 원소를 가지는 조합을 만들기 위해선 다음과 같이 짜면 된다.

string order = "ABCDE";
for (int i = 0; i < order.size(); i++)
{
    for (int j = i + 1; j < order.size(); j++)
    {
        for (int k = j + 1; k < order.size(); k++)
        {
            cout << order[i] << order[j] << order[k] << endl;
        }
    }
}

하지만 orders 배열의 각 원소는 크기가 2 이상 10 이하인 문자열이다. 그리고 course 배열의 각 원소는 2 이상 10 이하인 자연수이다.
모든 조합을 찾아야하므로 중첩 반복문으로 만들려면 2개부터 10개까지의 중첩을 하는 꽤 귀찮은 작업을 진행해야한다.

2. 조합만들기 - 라이브러리

algorithm 헤더에 있는 next_permutation을 사용하는 방법이다.
예를 들면 ABCDE에서 모든 조합을 만들기 위해선 다음과 같이 짜면 된다.

string order = "ABCDE";
vector<int> arr(order.size());
for (int i=2; i <= order.size(); i++)
{
    fill(arr.begin(), arr.end(), 0);
    for (int j=0; j < i; j++)
    {
        arr[j] = 1;
    }
    sort(arr.begin(), arr.end());

    do 
    {
        for (int index=0; index < arr.size(); index++)
        {
            if (arr[index])  cout << order[index];
        }    
        cout << endl;
    } while(std::next_permutation(arr.begin(), arr.end()));
    cout << endl;
}
// OUTPUT 
// DE
// CE
// CD
// BE
// BD
// BC
// AE
// AD
// AC
// AB

// CDE
// BDE
// BCE
// BCD
// ADE
// ACE
// ACD
// ABE
// ABD
// ABC

// BCDE
// ACDE
// ABDE
// ABCE
// ABCD

// ABCDE

조금 쉬운 방법이지만 초기화(fill이나 sort)를 계속 사용해야해서 비효율적이다.
그리고 next_permutation을 사용하면 알고리즘 스터디를 하는 이유가 없다.

 

나중에 생각난건데 bitmasking을 사용하면 비슷한 방법이 될 듯하다.

 

3. 조합만들기 - Backtracking, Recursive

내가 사용한 방법은 백트래킹을 사용한 방법이다.
visit 배열을 사용한 가지치기를 해서 중복되지 않는 조합을 모두 만들 수 있다.

void make_combination(
    string order, int start_index, int limit,
    unordered_map<string, int>& m
)
{
    // cout << start_index << " " <<limit <<endl;
    if (start_index == limit) return;
    for (int i = start_index; i < limit; i++)
    {
        if (visit[i]) continue;
        visit[i] = 1;
        insertItem(order,limit, m);
        make_combination(order, i + 1, limit, m);
        visit[i] = 0;
    }
}

 

알고리즘

1. orders에 있는 원소들을 순회하면서 모든 조합을 만든다.
   • map이나 unordered_map을 사용해서 조합이 몇번 만들어졌는지 저장한다.
   • max_count 배열도 만들어서 해당 길이에서의 최대 값(몇번 만들어졌는지)을 저장한다.
     • 입출력 예 1번으로 보면 max_count[2]=4, max_count[3]=3, max_count[4]=2 가 된다.
2. 만들어진 모든 조합을 순회하면서 조건에 맞는 값을 answer에 저장한다.
   • 각 조합의 길이가 course에 있는지 확인한다.
   • 만들어진 조합의 카운트가 2번 이상인지 확인한다. (딱 한번만 카운트 된 것은 제외한다.)
   • 길이별로 최대 카운트인 조합만 answer에 추가한다.

 

새로 알게된 것

1. map과 unordered_map의 차이

둘다 같은 메서드로 사용할수 있는데 구현되어있는 자료구조에 대해서 차이가 있다.

map은 트리(Red-Black Tree)를 사용한다. 추가, 탐색할 때 O(logN)이 걸린다. 모든 원소들이 정렬되어있다.

unordered_map(hash_map)은 해시테이블을 사용한다. 추가, 탐색할때 O(log1)이 걸린다. 원소들이 정렬되어있지 않다.

이 문제에서 어떤걸 사용해도 상관 없지만 map을 사용하면 answer에 추가할때 따로 정렬하지 않아도 된다.

2. 문자열 파싱

프로그래머스에서 진행할땐 테스트케이스를 쉽게 추가할수 있는데 vscode에서 gcc(g++)를 사용하면 테스트케이스부터 파싱해야한다.
fstream 을 사용해서 파일을 한 줄 씩 읽을수 있다. 한 줄 씩받은 문자열을 \t과 \n을 기준으로 다시 문자열로 나누고 그다음도 , 이나 "으로 나눠서 vector<string> 이나 vector<int>에 넣어 반환하는 것을 따로 만들었다.

문자열은 파이썬이 확실히 편하다. sys.stdin.readline(), string.split(',') 등등

 

전체 코드

#include <fstream>
#include <iostream>
#include <string>
#include <vector>

using namespace std;
void printVector(vector<string> v);
void printVector(vector<int> v);
vector<string> splitStringWithTab(string s);
vector<string> parsingVectorString(string s);
vector<int> parsingVectorInteger(string s) ;

/* -------------- programmers start -------------- */
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm> // sort, max
using namespace std;

vector<int> visit(21), max_count(21);
unordered_map<string, int> m; // m[combi] = count

void insertItem(string order, int limit)
{
    vector<char> tmp_v;
    string tmp;
    for (int i=0; i<limit; i++)
    {
        if (visit[i])
            tmp_v.push_back(order[i]);
    }
    sort(tmp_v.begin(), tmp_v.end());
    for (auto ch: tmp_v) tmp += ch;
    // insert item in map
    if (m[tmp]) m[tmp]++;
    else m[tmp] = 1;
    // renew max
    max_count[tmp.size()] = max(max_count[tmp.size()], m[tmp]);
}
void make_combination(string order, int start_index, int limit)
{
// cout << start_index << " " <<limit <<endl;
    if (start_index == limit) return;
    for (int i = start_index; i < limit; i++)
    {
        if (visit[i]) continue;
        visit[i] = 1;
        insertItem(order,limit);
        make_combination(order, i + 1, limit);
        visit[i] = 0;
    }
}
bool numberInCourse(int size, vector<int>& course)
{
    for (auto crs: course)
    {
        if (crs == size) return true;
    }
    return false;
}
vector<string> solution(vector<string> orders, vector<int> course) {
    // 1 init
    vector<string> answer;
    // 2 algorithm for combination
    for (auto order: orders)
    {
        make_combination(order, 0, order.size());
    }
    // 3 result
    for (auto mm: m)
    {
        if (!numberInCourse(mm.first.size(), course)) continue;
        if (mm.second < 2) continue; // if count 1, continue
        if (mm.second == max_count[mm.first.size()])
        answer.push_back(mm.first);
    }
    sort(answer.begin(), answer.end());
    return answer;
}

/* -------------- programmers end -------------- */

int main()
{
    ifstream fin;
    fin.open("./KODONGGUN/2_WEEK/programmers_menu_renewal_input.txt");
    if (!fin.is_open())
    {
        cout << "error" << endl;
        return EXIT_FAILURE;
    }

    vector<string> answer, result, orders, lineVector;
    vector<int> course;
    string line;
    string tmp;
    while(true)
    {
        getline(fin, line);
        if (line == "") break;
        lineVector = splitStringWithTab(line);
        orders = parsingVectorString(lineVector[0]);
        course = parsingVectorInteger(lineVector[1]);
        answer = parsingVectorString(lineVector[2]);
        result = solution(orders, course);
        cout << "result == answer: " << (result == answer?"true":"false") << endl;
    }
    fin.close();
    return 0;
}

void printVector(vector<string> v)
{
    for (auto item: v)
        cout << item << " ";
    cout << endl;
}

void printVector(vector<int> v)
{
    for (auto item: v)
        cout << item << " ";
    cout << endl;
}

vector<string> splitStringWithTab(string s)
{
    vector<string> ret_vector;
    string tmp = "";
    for (size_t i = 0; i < s.size(); i++)
    {
        if (s[i] == '\t' || s[i]== '\0')
        {
            ret_vector.push_back(tmp);
            tmp = "";
        }
        else
        {
            tmp += s[i];
        }
    }
    ret_vector.push_back(tmp);
    return ret_vector;
}

vector<string> parsingVectorString(string s)
{
    vector<string> ret_vector;
    string item = "";
    bool setItem = false;
    for (size_t i = 1; i < s.size()-1; i++)
    {
        if (setItem)
        {
            if (s[i] == '\"')
            {
                setItem = false;
                ret_vector.push_back(item);
                item = "";
            }
            else        
                item += s[i];
        }
        else
        {
            if (s[i] == '\"')            setItem = true;
            else                        continue;
        }
    }
    return ret_vector;
}

vector<int> parsingVectorInteger(string s)
{
    vector<int> ret_vector;
    string item = "";
    for (size_t i = 1; i < s.size()-1; i++)
    {
        if (s[i] == ',')
        {
            ret_vector.push_back(stoi(item));
            item = "";
        }
        else
        {
            item += s[i];
        }
    }
    ret_vector.push_back(stoi(item));

    return ret_vector;
}

---

참고한 글

[C++ STL] 순열과 조합 (next_permutation)