[ 프로그래머스 단체사진 찍기 (Lv2) ] (C++)

프로그래머스의 단체사진 찍기 (Lv2) 문제이다.

[ 문제풀이 ]

본인은 문제를 보고 크게 2가지 파트로 나누어서 진행하였다.

1. 순열 구현하기

2. 문제의 조건에 맞는 경우 찾기

먼저 첫 번째 파트를 보자. "순열 구현하기"

왜 순열을 구현하는 것일까 ?? 주어진 8명의 사람을 순서가 존재하는 수열로 나타냈을 때 발생할 수 있는 모든 경우의 수에서

문제의 조건에 맞는 경우만 정답으로 체크해주기 위해서이다.

그렇다면 왜 조합이 아니고 순열일까 ?? 왜냐하면 순서에 영향을 미치기 때문이다.

예를 들어서 { 1, 2, 3 } 으로 줄을 서는 경우와 , { 2, 3, 1 } 로 줄을 서는 경우를 보자.

그리고 문제의 조건으로 "1번 사람과 3번 사람은 2칸 이상 떨어져 있길 원합니다" 라는 조건이 주어진다면, 첫 번째 경우는

정답으로 체크가 되지만, 두 번째 경우는 정답으로 체크가 되질 않는다.

즉 ! 순서에 영향을 미치는 수열인 '순열'을 구현해 주어야 한다. 또한, 모든 경우를 다 탐색해봐도 된다고 생각한 것은

주어진 크기가 8이기 때문에 순열로 나타냈을 때 발생 가능한 경우의 수는 8 ! 이 되고, 약 40000개로 충분히 탐색해볼 만한

경우의 수 이기 때문이다.

아직 순열에 대해서 잘 모른다면 아래의 글을 읽고 오도록 하자.

[ 순열 구현하는법 알아보기 (Click) ]

이렇게 첫 번째 파트에서 순열을 구했다면 이제 그 순열이 정답에 조건을 만족시키는 순열인지 파악해보면 된다.

조건에는 3가지 조건이 있다.

'=', '<', '>'

먼저 '=' 조건을 보자. A ~ B = x 라고 한다면, A와 B는 정확하게 x + 1칸 떨어져 있기를 원한다는 것이다.

예를 들어서 A ~ B = 0 이라는 입력이 주어진다면 A와 B는 0칸 떨어져 있길 원한다 라는 것이 아니고, 1칸 떨어져 있길 원한다

라는 것을 의미하게 된다. 즉 ! A ~ B = x 라고 주어진다면, 이 x의 값을 + 1 시켜서 계산을 해주어야 한다.

'<' 조건과 '>' 조건을 보게 되면 마찬가지로 + 1 시켜서 계산을 진행해 주어야 한다.

A ~ B > x 가 의미하는 것은, A와 B가 x 칸 이상 떨어져 있길 원한다 라는 것이고, 이는 실제로는 x + 1칸 떨어져 있길

원한다는 것을 의미하게 된다. 따라서 + 1 시켜서 계산을 진행해주면 된다.

[ 소스코드 ]

#include <string>
#include <vector>
using namespace std;
 
int Answer;
bool Select[8];
char ItoC[8] = { 'A','C','F','J','M','N','R','T' };
 
void DFS(int Cnt, char Arr[], vector<string> data)
{
    if (Cnt == 8)
    {
        for (int i = 0; i < data.size(); i++)
        {
            char N1 = data[i][0];
            char N2 = data[i][2];
            char Cond = data[i][3];
            int Dist = data[i][4] - '0';
            Dist++;
 
            int Idx, IIdx;
            Idx = IIdx = -1;
            for (int j = 0; j < 8; j++)
            {
                if (Arr[j] == N1) Idx = j;
                if (Arr[j] == N2) IIdx = j;
                if (Idx != -1 && IIdx != -1) break;
            }
 
            if (Cond == '=' && abs(Idx - IIdx) != Dist) return;
            if (Cond == '<' && abs(Idx - IIdx) >= Dist) return;
            if (Cond == '>' && abs(Idx - IIdx) <= Dist) return;
        }
        Answer++;
        return;
    }
    
    for (int i = 0; i < 8; i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        Arr[Cnt] = ItoC[i];
        DFS(Cnt + 1, Arr, data);
        Select[i] = false;
    }
}
 
int solution(int n, vector<string> data)
{
    char Arr[8] = { NULL, };
    Answer = 0;
    DFS(0, Arr, data);
    return Answer;
}