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

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

전역 변수로 int answer = 0; 으로 선언해놓아서 초기화했다고 생각했는데, 그게 안되나보다... 그래서 제출을 몇번했는데 계속 실패하길래 설마해서 int solution(... 안에서 answer = 0을 적어주니 바로 통과했다;

쓸데없이 알파벳이 ACFJMNRT 이런식으로 되어 있어서 이를 0~7로 mapping해줄 map 자료구조를 하나 사용했고, 그 외에는 DFS로 조합을 구하는 일반적인 코드이다.

코드는 아래와 같다.

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

using namespace std;

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.

char candidate[8];
int visit[8] = { 0, 0, 0, 0, 0, 0, 0, 0 };
int answer;
void dfs(int n, int depth, const string &str, const vector<string> &data, const map<char, int> &m)
{
    if(n == depth) {
        map<char, int> candidate_map;
        for(int i=0;i<depth;i++) 
            candidate_map[candidate[i]] = i;

        for(int i=0;i<data.size();i++) {
            char from = data[i][0];
            char to = data[i][2];
            char op = data[i][3];
            int dist = 1 + data[i][4] - '0';
            int f = candidate_map[data[i][0]];
            int t = candidate_map[data[i][2]];
            if(op == '=') {
                if(abs(f - t) != dist) 
                    return;
            } else if(op == '<') {
                if(abs(f - t) >= dist)
                    return;
            } else {
                if(abs(f - t) <= dist) 
                    return;
            }
        }
        answer++;
        return;
    }
    
    for(int i=0;i<8;i++) {
        if(visit[i] == 1)
            continue;
        visit[i] = 1;
        candidate[depth] = str[i];
        dfs(n, depth + 1, str, data, m);
        visit[i] = 0;
    }
}
int solution(int n, vector<string> data) {
    answer = 0;
    string str = "ACFJMNRT";
    map<char, int> m;
    for(int i=0;i<8;i++) 
        m[str[i]] = i;
    
    dfs(8, 0, str, data, m);
    
    return answer;
}

다른 코드를 좀 참고해보니

string str = "ACFJMNRT"

do {
...
	이 안에서 str을 사용하면 됨.
...
} while(next_permutation(str.begin(), str.end()));

위와 같은 식으로 코드를 짜면 조합 구하는 코드가 훨씬 깔끔할 것 같다.

아래는 next_permutation으로 구현한 코드이다.
0.13s로 크게 차이나진않는데 코드가 깔끔한 것 같다.

#include <string>
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

int solution(int n, vector<string> data) {
    int answer = 0;
    string str = "ACFJMNRT";
    do {
        map<char, int> candidate_map;
        for(int i=0;i<8;i++) 
            candidate_map[str[i]] = i;
        
        bool right = true;
        for(int i=0;i<data.size();i++) {
            char from = data[i][0];
            char to = data[i][2];
            char op = data[i][3];
            int dist = 1 + data[i][4] - '0';
            int f = candidate_map[data[i][0]];
            int t = candidate_map[data[i][2]];
            if(op == '=') {
                if(abs(f - t) != dist) {
                    right = false;
                    break;
                }
            } else if(op == '<') {
                if(abs(f - t) >= dist) {
                    right = false;
                    break;
                }
            } else {
                if(abs(f - t) <= dist) {
                    right = false;
                    break;
                }
            }
        }
        if(right)
            answer++;
    } while(next_permutation(str.begin(), str.end()));

    return answer;
}