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

2017 카카오코드 본선

 

 

사람이 8명 뿐이다.

모든 사람을 줄세우는데 O(8!) 만큼의 시간이 걸릴 것이다.

따라서 백트래킹으로 모든 경우를 탐색해도 시간내에 충분히 풀린다.

 

 

백트래킹 부분

void sorting(int cnt, int &answer, vector<string> &data, map<char, int> &m){
    if(cnt == 8){
        if(is_valid(data, m)){
            answer++;
        }
        return;
    }
    
    for(int i = 0; i < 8; i++){
        if(visited[i]) continue;
        visited[i] = cnt+1;
        sorting(cnt+1, answer, data, m);
        visited[i] = 0;
    }
}

중요한 부분은 visited배열의 정의이다.

 

visited배열의 인덱스는 사람의 번호이다. 이때 값으로 인덱스에 해당하는 번호의 사람이 줄의 몇 번째에 들어갔는지가 들어간다.

cnt가 줄의 몇 번째인지를 나타낸다.

 

cnt가 8이 되어서 현재 줄을 선 모양새가 문제에서 요구하는 조건에 일치한다면 답을 +1 증가시킨다.

 

 

줄 선 모양새 판별

bool is_valid(vector<string> &data, map<char, int> &m){
    for(int i = 0; i < data.size(); i++){
        int target1 = visited[m[data[i][0]]];
        int target2 = visited[m[data[i][2]]];
        char op = data[i][3];
        int xop = data[i][4] - '0';
        
        if(op == '='){
            if(abs(target1 - target2) == xop + 1) continue;
            else return false;
        }
        else if(op == '>'){
            if(abs(target1 - target2) > xop + 1) continue;
            else return false;
        }
        else if(op == '<'){
            if(abs(target1 - target2) < xop + 1) continue;
            else return false;
        }
    }
    
    return true;
}

위 코드에는 안나와있지만 map 자료구조를 사용해서 사람의 이름(A, C, F, J ...)에 맞게 사람의 id 값을 저장해 놓았다.

 

int target1 = visited[m[data[i][0]]];
int target2 = visited[m[data[i][2]]];

data[i][0]과 data[i][2]는 문제에서 주어진 조건에 나오는 사람이다.

m[data[i][0]]을 해주면 그 사람의 id를 알 수 있다.

m[data[i][0]]를 id라고 하겠다.

 

visited[id]를 해주면 해당 id인 사람이 몇 번째로 줄을 섰는지 알 수 있다!

이제 문제는 거의 다 풀었다.

 

연산자에 맞게 조건이 맞는지를 확인해주면 된다.

 

 

 

최종 코드

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

using namespace std;


// char kakao[9] = {'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'};
int visited[9];

void map_insert(map<char, int> &m){
    m.insert({'A', 0});
    m.insert({'C', 1});
    m.insert({'F', 2});
    m.insert({'J', 3});
    m.insert({'M', 4});
    m.insert({'N', 5});
    m.insert({'R', 6});
    m.insert({'T', 7});
}

bool is_valid(vector<string> &data, map<char, int> &m){
    for(int i = 0; i < data.size(); i++){
        int target1 = visited[m[data[i][0]]];
        int target2 = visited[m[data[i][2]]];
        char op = data[i][3];
        int xop = data[i][4] - '0';
        
        if(op == '='){
            if(abs(target1 - target2) == xop + 1) continue;
            else return false;
        }
        else if(op == '>'){
            if(abs(target1 - target2) > xop + 1) continue;
            else return false;
        }
        else if(op == '<'){
            if(abs(target1 - target2) < xop + 1) continue;
            else return false;
        }
    }
    
    return true;
}

void sorting(int cnt, int &answer, vector<string> &data, map<char, int> &m){
    if(cnt == 8){
        if(is_valid(data, m)){
            answer++;
        }
        return;
    }
    
    for(int i = 0; i < 8; i++){
        if(visited[i]) continue;
        visited[i] = cnt+1;
        sorting(cnt+1, answer, data, m);
        visited[i] = 0;
    }
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, vector<string> data) {
    memset(visited, 0, sizeof(visited));
    int answer = 0;
    map<char, int> m;
    map_insert(m);
    
    sorting(0, answer, data, m);
    
    return answer;
}