오늘은 C/C++로 알고리즘을 풀 때 종종 사용되는 순열 구하는 방법에 대해서 정리하려 한다.

순열이란 쉽게 말해 특정 배열의 요소들로 만들 수 있는 조합들의 집합이라고 할 수 있다. 예를 들어 배열에 ['A', 'B', 'C'] 와 같이 담겨져 있을 경우 순열들은 "ABC", "ACB", "BAC", "BCA", "CAB", "CBA"가 될 수 있다. 굉장한 정성으로 직접 일일이 하드코딩 할 수 있긴 하지만 귀찮은건 참을 수 없으므로 필자는 더 쉬운 방법을 찾아 공부한다.

 C/C++에서는 이 순열을 아주 쉽게 사용할 수 있도록 미리 만들어진 next_permutation() 함수가 있다. algorithm.h 해더파일 안에 정의되어 있는 함수로 특정 구간 iterator를 아규먼트로 전달해주면 특정 구간의 요소들을 순열로 만들어 준다. 만약에 더 이상 순열의 경우가 없을 경우 false를 리턴하고 있을 경우 true를 리턴한다. 이 next_permutation() 함수를 사용하기 전에 중요한 요소가 있다. 바로 next_permutation()에 전달되는 특정 구간의 요소들은 오름차순으로 정렬되어 있어야한다.

 아래는 최근 풀었던 알고리즘 중 이 next_permutation() 함수를 활용해서 풀었던 문제다. 프로그래머스에서 직접 풀 수 있으며 2021 카카오 블라인드 테스트의 메뉴 리뉴얼 문제이다.

#include <bits/stdc++.h>
 
using namespace std;
 
bool compare(pair<string, int> p1, pair<string, int> p2) {
    return p1.second > p2.second;
}
 
vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    
    unordered_map<string, int> courseMap;
    for (int i = 0; i < orders.size() - 1; i++) {
        for (int j = i + 1; j < orders.size(); j++) {
            vector<char> s;
            for (int k = 0; k < orders[j].length(); k++) {
                if (orders[i].find(orders[j][k]) != string::npos) s.push_back(orders[j][k]);
            }
            if (s.size() < 2) continue;
            
            for (int c = 0; c < course.size(); c++) {
                sort(s.begin(), s.end());
                do {
                    if (s.size() < course[c]) break;
                    string croped(s.begin(), s.begin() + course[c]);
                    vector<char> tmp(croped.begin(), croped.end());
                    sort(tmp.begin(), tmp.end());
                    string sorted(tmp.begin(), tmp.end());
                    courseMap[sorted]++;
                } while(next_permutation(s.begin(), s.end()));
            }
        }
    }
    
    for (auto it = courseMap.begin(); it != courseMap.end(); it++) it->second = 0;
    for (auto it = courseMap.begin(); it != courseMap.end(); it++) {
        for (int i = 0; i < orders.size(); i++) {
            string target = it->first;
            bool isEquals = true;
            for (int j = 0; j < target.length(); j++) {
                if (orders[i].find(target[j]) == string::npos) isEquals = false;
            }
            if (isEquals) courseMap[target]++;
        }
    }
    
    for (int i = 0; i < course.size(); i++) {
        vector<pair<string, int>> result;
        for (auto it = courseMap.begin(); it != courseMap.end(); it++) {
            if (it->first.length() == course[i] && it->second >= 2) {
                 result.push_back(*it);
            }
        }
        if (result.size() == 0) continue;
        
        sort(result.begin(), result.end(), compare);
        answer.push_back(result[0].first);
        for (int i = 1; i < result.size(); i++) {
            if (result[0].second == result[i].second) {
                answer.push_back(result[i].first);
            } else break;
        }
    }
    
    sort(answer.begin(), answer.end());
    return answer;
}

 22번째 줄처럼 next_permutation() 함수를 사용하기 전에 오름차순으로 정렬한 부분을 볼 수 있고 while 반복문을 통해 순열 경우의 수가 없을 때까지 반복해서 사용하고 있다. 이 문제는 아래의 링크에서 직접 풀어볼 수 있다.

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