단체사진 찍기 - Level 4

해결방법

경우의 수를 구하는 문제이다. 다행히 n의 최대크기가 8이므로 8! = 40,320개로 모든 경우의수를 세면서 풀 수 있는 문제이다. 이 문제를 풀면서 next_permutation이라는 함수를 새로 배웠다. 그 동안 재귀나 반복으로 풀었는데, 한결 쉬워질거 같다.
먼저 vector에다가 8개의 수를 모두 넣었다. 그리고 pos배열을 하나 만들어 해당 알파벳의 index번호를 넣었다.

 vector<char> f = {'A', 'C', 'F', 'J', 'M', 'N', 'R','T'};
 int pos[26];

그 다음 do ~ while문을 통해 나오는 다음 경우의 수를 통해 문제의 조건과 일치한다면 answer를 하나 높여주는 식으로 풀었다. 중요한 부분은 거리를 계산하는 것인데, 내가 문제를 처음에는 단순히 2개 사이의 거리를 계산했지만 알고보니 2명 사이에 몇명이 있는지가 문제였다. 따라서 -1를 해줘야 맞는 정답이 나온다.

     do {
        for(int i = 0; i < f.size(); ++i)
            pos[f[i] - 'A'] = i;
        bool possible = true;
        for(int d = 0; d < data.size(); ++d) {
            int c1 = data[d][0] - 'A';
            int c2 = data[d][2] - 'A';
            int dis = abs(pos[c1] - pos[c2]) - 1;
            char oper = data[d][3];
            int t = data[d][4] - '0';
            switch(oper) {
                case '=' :
                    if(dis != t) possible = false;
                    break;
                case '<' :
                    if(dis >= t) possible = false;
                    break;
                case '>' :
                    if(dis <= t) possible = false;
                    break;
            }
            if(!possible)
                break;
        }
        if(possible) answer++;
    } while(next_permutation(f.begin(), f.end()));

전체코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int pos[26];
int solution(int n, vector<string> data) {
    int answer = 0;
    vector<char> f = {'A', 'C', 'F', 'J', 'M', 'N', 'R','T'};
    do {
        for(int i = 0; i < f.size(); ++i)
            pos[f[i] - 'A'] = i;
        bool possible = true;
        for(int d = 0; d < data.size(); ++d) {
            int c1 = data[d][0] - 'A';
            int c2 = data[d][2] - 'A';
            int dis = abs(pos[c1] - pos[c2]) - 1;
            char oper = data[d][3];
            int t = data[d][4] - '0';
            switch(oper) {
                case '=' :
                    if(dis != t) possible = false;
                    break;
                case '<' :
                    if(dis >= t) possible = false;
                    break;
                case '>' :
                    if(dis <= t) possible = false;
                    break;
            }
            if(!possible)
                break;
        }
        if(possible) answer++;
    } while(next_permutation(f.begin(), f.end()));
    return answer;
}