[프로그래머스 LV2] 단체사진 찍기 (조합) / 2017 카카오 코드 본선) [C++]

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

코딩테스트 연습 - 단체사진 찍기

algorithm STL의 next_permutation의 존재를 알게 된 문제다.

 

항상 순열이나 조합을 직접 구현해서 사용했었는데 종종 사용하면 편할 것 같다.

 

매번 순열을 구한 뒤, 주어진 조건에 해당하는지 확인 후 확인하면 개수를 세주는 식으로 진행하면 된다.

 

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

using namespace std;

bool rightDistance(int between, char comp, int distance){
    if(comp == '='){
        return between == distance;
    }
    else if(comp == '>'){
        return between > distance;
    }
    else if(comp == '<'){
        return between < distance;
    }
}

int solution(int n, vector<string> data) {
    int answer = 0;
    string s = "ACFJMNRT";
    do{
        int flag = true;
        for(int i = 0 ; i < data.size() ; i++){
            char c1 = data[i][0];
            char c2 = data[i][2];
            char comp = data[i][3];
            int distance = data[i][4]-'0';
            
            int between = s.find(c1) - s.find(c2); 
            // 붙어있는 경우는 distance 0이므로 -1
            if(!rightDistance(abs(between)-1, comp, distance)){
                flag = false;
                break;
            }
        }
        if(flag)
            answer++;
    }
    while(next_permutation(s.begin(), s.end()));
    
    return answer;
}

둘 사이에 거리가 1보다 떨어져 있으면 좋겠다는 조건은 실제 문자열에서 인덱스 차이가 2여야 한다.

인덱스 차이가 1인 상태는 서로 붙어있는 상황이기 때문이다.

 

또한 next_permutation은 오름차순 되어 있는 배열이나 문자열 등에 적용해야 모든 순열을 찾을 수 있다.

아니면 오름차순 되는 구간부터 순열을 뱉어낼 것이다.