[2023년 11월 25일]단체사진 찍기(43분)

https://school.programmers.co.kr/learn/courses/30/lessons/1835

구현 아이디어 4분 구현 39분

풀이

저번에는 map을 활용하지 않았기 때문에 조건으로 들어오는 "N~F=2"에 관해 N이 위치한 인덱스, F가 위치한 인덱스를 일일이 찾아야 했다.

이번에는 map을 활용해서 map의 key에 캐릭터의 이름, value에 해당 캐릭터의 인덱스를 넣어 더 빠른 탐색이 가능하게 구현해 봤다.

#include <string>
#include <vector>
#include <map>

using namespace std;

int check[8];
char character[8];
int answer;

void DFS(int L, int e, map<char, int>& m, const vector<string>& data)
{
    if(L == e)
    {
        //for(auto it : m)
            //printf("%d ", it.second);
        //printf("\n");
        
        // 조건 확인.
        for(int i = 0; i < data.size(); ++i)
        {
            string cond = data[i];
            char p1 = data[i][0];
            char p2 = data[i][2];
            char op = data[i][3];
            char cd = data[i][4];
            
            int p1_idx = m[p1];
            int p2_idx = m[p2];
            
            if(op == '=' && !(abs(p1_idx - p2_idx) - 1 == cd - '0'))
                return;
            
            else if(op == '<' && !(abs(p1_idx - p2_idx) - 1 < cd - '0'))
                return;
            
            else if(op == '>' && !(abs(p1_idx - p2_idx) - 1 > cd - '0'))
                return;
        }
        
        ++answer;
    }
    else
    {
        for(int i = 0; i < 8; ++i)
        {
            if(check[i] == 0)
            {
                check[i] = 1;
                m[character[L]] = i;
                DFS(L + 1, e, m, data);
                check[i] = 0;
            }
        }
    }
}

int solution(int n, vector<string> data) {
    answer = 0;
    
    character[0] = 'A';
    character[1] = 'C';
    character[2] = 'F';
    character[3] = 'J';
    character[4] = 'M';
    character[5] = 'N';
    character[6] = 'R';
    character[7] = 'T';
    
    for(int i = 0; i < 8; ++i) check[i] = 0;
    
    // char이 몇 번째에 위치해 있는지.
    map<char, int> m;
    
    DFS(0, 8, m, data);
    
    return answer;
}