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

문제 설명

카카오 프렌즈 8명이 단체사진을 찍습니다.
100개 이하의 멤버 간 거리 조건이 주어집니다.
예) [N~F=0, R~T>2]

아이디어

8명이라 부르트포스적(next_permutation으로 하나의 certification을 생성한다)으로 풀었을 때 8! = 40320개의 경우(순열)가 나온다.
이 경우들에 대해 최대 100개의 조건들이 해당 되는지 확인을 하는 부르트포스 방법이 가장 먼저 떠올랐다.

또 다른 아이디어 - 구현하기에 넘 복잡함

고딩 때 이런 종류의 문제를 확통 과목에서 많이 접했다.
그 때는 경우의 수 계산 공식을 사용해 풀었던 거 같다.

예) 무지와 콘은 붙어있어야합니다.
무지와 콘을 하나의 덩어리로 보고 (8-1)!

비슷한 느낌으로 풀 수 있지 않을까 고민을 해봤는데 조건들이 100개까지 될 수 있어서 뒤에 조건을 따질 땐 앞 조건을 신경써야할 것 같아 안 좋았던 것 같다.

예) 무지와 콘은 붙어있어야합니다. 그리고 라이언과 어피치의 간격은 2 이상입니다.
의 경우 라이언 어피치 사이에 무지 콘이 들어가는 경우까지 신경 써얗ㄴ다.

셋으로 제외된, 혹은 아직 조건에 의해 걸러지지 않은 사진 순서들을 관리하고 중복 제외를 방지하면 조건을 1회독만으로 끝낼 수 있다고 생각도 했는데.. 이를 위해선 또 next_permutation으로 하나의 certification을 표현할 수 있어야해서 맨 처음의 아이디어를 쓰기로 했다.

삽질

분명 구현전에는 생각했던 건데 거리를 계산할 때 그냥 위치의 뺄셈을 하는 것이 아니라 뺄셈 한 결과에서 -1을 해주어야한다.(나란히 서있을 때 거리는 0이니까)

코드

#include <string>
#include <vector>
#include<math.h>
#include<iostream>
#include<algorithm>
using namespace std;

int solution(int n, vector<string> data) {
    int answer = 0;
    char candies[] = {'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'};

    do{
        int cvtidx[26];
        for(int i =0;i<8;i++){
            cvtidx[candies[i]-'A'] = i;
        }
        bool valid = true;
        for(int i = 0;i<n;i++){
            string command = data[i];
            int a = command[0]-'A', b = command[2]-'A';
            char op = command[3];
            int dist = command[4]-'0';
            int cdist = abs(cvtidx[a]-cvtidx[b])-1;
    
            if((op=='='&&cdist!=dist)||(op =='<'&&cdist>=dist)
            ||(op =='>'&&cdist<=dist)){
                valid = false;
                break;
            }
        }
        if(valid) {
            answer++;
        }
    }while(next_permutation(candies,candies+8));
    return answer;
}