순열

코딩테스트의 주요 유형 중 하나인 브루트 포스를 풀때,

순열(Permutation) 개념을 이용하면, 필요한 모든 경우의 수를 구할 수 있을때가 있다.

 

C++ 에서는 Algorithm 헤더 파일에 

next_permutation 과 prev_permutation 함수가 제공된다.

 

 

- next_permutation()

template< class BidirIt >
bool next_permutation( BidirIt first, BidirIt last );

next_permutation 은 위와 같은 형식을 따르며, 리턴 타입은 bool 이다.

 

 

- 예시 코드

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    vector<int> v(4);
    for (int i = 0; i < 4; ++i) v[i] = i + 1;
    
    do {
        for (int i = 0; i < 4; ++i) cout << v[i] << " ";
        cout << "\n";
    } while(next_permutation(v.begin(), v.end());
    
    return 0;
}
 
/*
    실행 결과
    1 2 3 4
    1 2 4 3
    .....
    4 3 2 1
*/

 

 

- prev_permutation

template< class BidirIt >
bool prev_permutation( BidirIt first, BidirIt last);

 

next_permutation 과 동일하게 bool 타입을 리턴타입으로 가지며, 

next_permutation 과는 반대로 진행한다고 보면 된다.

 

 

- 예시 코드

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    vector<int> v(4);
    for (int i = 0; i < 4; ++i) v[i] = i + 1;
    
    do {
        for (int i = 0; i < 4; ++i) cout << v[i] << " ";
        cout << "\n";
    } while(prev_permutation(v.begin(), v.end());
    
    return 0;
}
 
/*
    실행 결과
    4 3 2 1
    4 3 1 2
    .....
    1 2 3 4
*/

 

 

 

- 순열을 사용한 브루트 포스 문제

programmers.co.kr/learn/courses/30/lessons/67257

코딩테스트 연습 - 수식 최대화

 

 

- c++

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
void divide(string& exp, vector<ll>& nums, vector<char>& ops) {
    ll num = 0;
    for (int i = 0; i < exp.length(); ++i) {
        if (exp[i] >= '0') {   // 숫자 일때
            num *= 10;
            num += exp[i] - '0';
        } else {              // 연산자 일때
            nums.push_back(num);
            ops.push_back(exp[i]);
            num = 0;
        }
    }
    nums.push_back(num); // 중위 표기식이므로 맨 뒤에 연산자가 오지 않기때문에, push_back 을 호출.
}
 
ll cal(ll num1, ll num2, char op) {
    if (op == '+') return num1 + num2;
    else if (op == '-') return num1 - num2;
    else if (op == '*') return num1 * num2;
    return -1;
}
 
long long solution(string expression) {
    long long answer = 0;
    
    vector<ll> nums;
    vector<char> ops;
    divide(expression, nums, ops);
    
    string opOrder = "+-*";
    sort(opOrder.begin(), opOrder.end()); // 순열 구현을 위한 사전 정렬
    
    do {
        queue<ll, deque<ll>> numQ2, numQ1(deque<ll>(nums.begin(), nums.end()));
        queue<char, deque<char>> opQ2, opQ1(deque<char>(ops.begin(), ops.end()));
        
        for (int i = 0; i < 3; ++i) {
            ll temp = numQ1.front();
            numQ1.pop();
            
            while(!opQ1.empty()) {
                if (opQ1.front() == opOrder[i]) // 현재 순서의 연산자가 순열 순차와 일치할때.
                    temp = cal(temp, numQ1.front(), opQ1.front());
                else {                         // 현재 순서의 연산자가 순열 순차와 불일치 할때
                    opQ2.push(opQ1.front());   // 우선순위가 불일치하는 연산자를 넣고
                    numQ2.push(temp);          // 여태까지 계산한 결과 값을 다른 큐에 넣어둠
                    temp = numQ1.front();
                }
                opQ1.pop();
                numQ1.pop();
            }
            numQ2.push(temp);
            
            if (numQ2.size() == 1) answer = max(abs(numQ2.front()), answer);
            numQ1.swap(numQ2);
            opQ1.swap(opQ2);
        }
        
    } while(next_permutation(opOrder.begin(), opOrder.end()));
    
    return answer;
}

 

 

 

* 코드 참조

softworking.tistory.com/435

[프로그래머스]2020 카카오 인턴십 : 수식 최대화 (level 2) (c++)