[Programmers] Lv2. 단체사진 찍기 | C++

🔗문제 보러가기

프로그래머스

 

👨‍💻풀이 과정

 

저는 DFS를 이용하여 8명의 캐릭터들의 순열마다 조건식을 검사하였습니다. 한 가지 실수했던 게, 조건식의 다섯번째 글자에 해당하는 간격은 두 캐릭터 사이의 캐릭터 숫자라는 걸 까먹었습니다. 저처럼 인덱스 탐색 방식으로 할 시, 간격에다가 -1을 해주는 추가 작업이 필요합니다.

int distance = abs(sourceIndex - targetIndex) - 1;

 

✏️소스 코드 및 결과

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const vector<char> friends{ 'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T' };
vector<bool> used(friends.size(), false);

struct Constraint
{
    Constraint() { }
    Constraint(char source, char target, char operator_, int distance) : _source(source), _target(target), _operator(operator_), _distance(distance) { }
    char _source;
    char _target;
    char _operator;
    int  _distance;
};

bool IsOk(int difference, int distance, char _operator)
{
    switch (_operator)
    {
    case '=':
        return difference == distance;
    case '<':
        return difference < distance;
    case '>':
        return difference > distance;
    }

    return false;
}

void DFS(const vector<Constraint>& constraints, vector<char>& sequence, int& answer)
{
    if (sequence.size() == friends.size())
    {
        bool isOk = true;

        for (const auto& constraint : constraints)
        {
            int sourceIndex = std::distance(sequence.begin(), std::find(sequence.begin(), sequence.end(), constraint._source));
            int targetIndex = std::distance(sequence.begin(), std::find(sequence.begin(), sequence.end(), constraint._target));
            int difference = abs(sourceIndex - targetIndex) - 1;

            if (!IsOk(difference, constraint._distance, constraint._operator))
            {
                isOk = false;
                break;
            }
        }

        if (isOk)
            answer++;
        return;
    }

    for (int i = 0; i < friends.size(); i++)
    {
        if (used[i])
            continue;

        sequence.push_back(friends[i]);
        used[i] = true;

        DFS(constraints, sequence, answer);
        used[i] = false;
        sequence.pop_back();
    }
}

int solution(int n, vector<string> data) {
    int answer = 0;
    vector<Constraint> constrains;
    vector<char> sequence;

    for (const auto& constraint : data)
        constrains.emplace_back(Constraint(constraint[0], constraint[2], constraint[3], constraint[4] - '0'));

    DFS(constrains, sequence, answer);
    return answer;
}

 

 

 

vector<char>말고 그냥 string으로 사용했었어도 될 것 같네요. 캐릭터들을 나타내는 표현 또한 문자이므로 오름차순 정렬이 가능하니, next_permutation() 함수를 사용했으면 더 깔끔했을 것 같습니다.