[프로그래머스] 단체사진 찍기

문제 링크

 

접근법

멤버의 모든 조합을 체크하면 되기 때문에 C++의 경우 next_permutation이라는 함수를 이용하면 비교적 쉽게 풀 수 있습니다. 주어지는 조건을 '모두' 충족하는 경우의 수를 찾는 문제입니다. next_permutation 함수를 쓰기 위해선 오름차순이 되어 있어야 합니다. 그래서 멤버의 문자열을 만들어 줄 때 오름차순으로 정렬되도록 초기화했습니다.

 

조금 편하게 풀고자 전역 변수 두 개를 뒀습니다. max, min, abs 같은 간단한 함수는 라이브러리를 쓰지 않는 편입니다. 물론 복잡한 기능의 경우에는 라이브러리를 사용하는 것이 당연히 낫습니다. 가령 min, max를 구할 때 C++11부터는 파라미터에 initializer_list가 있어서 중괄호를 이용해서 세 개 이상의 값을 넣을 수 있어 편합니다. 거리를 구할 때 1을 빼는 이유는 바로 붙어 있는 경우가 거리가 0인 것 해당하는데

인덱스 차이는 1이기 때문입니다.

 

코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

vector<string> condition;
int N;

int get_abs(int val)
{
    return val < 0 ? -val : val;
}

bool is_correct(string& member)
{
    for (int i = 0; i < N; ++i)
    {
        bool flag = false;
        auto f1 = condition[i][0];
        auto f2 = condition[i][2];
        auto op = condition[i][3];
        auto dist = condition[i][4] - '0';
        
        auto diff = get_abs(member.find(f1) - member.find(f2)) - 1;
        if (op == '=')
            flag = dist == diff ? true : false;
        else if (op == '<')
            flag = diff < dist ? true : false;
        else if (op == '>')
            flag = diff > dist ? true : false;
        if (!flag)
            return false;
    }
    return true;
}

int solution(int n, vector<string> data) 
{
    int answer = 0;
    string member = "ACFJMNRT";
    condition = data;
    N = n;
    do
    {
        if (is_correct(member))
            ++answer;
    } while (next_permutation(begin(member), end(member)));
    return answer;
}