프로그래머스 - 단체사진 찍기(2017 카카오코드 본선)

단체사진을 찍는 인원은 우선 총 8명이고 8명이 설 수 있는 경우의 수는 총 8! = 40320개이다. 그 중 최대 100개의 조건을 만족하는 순서쌍의 개수를 구하는 것이 문제이다.

 

코드

#include <string>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
map<char, int> m;
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, vector<string> data) {
    int answer = 0;
    string s = "ACFJMNRT";
    do{
        for(int i=0; i<s.size(); i++)
            m[s[i]] = i;
        bool flag = true;
        for(int i=0; i<data.size(); i++)
        {
            char a = data[i][0];
            char b = data[i][2];
            int dist = abs(m[a] - m[b]) - 1;
            if (data[i][3] == '=')
            {
                if (dist != data[i][4] - '0')
                {
                    flag = false;
                    break;
                }
            }
            else if (data[i][3] == '>')
            {
                if (dist <= data[i][4] - '0')
                {
                    flag = false;
                    break;
                }
            }
            else if (data[i][3] == '<')
            {
                if (dist >= data[i][4] - '0')
                {
                    flag = false;
                    break;
                }
            }
        }
        if (flag)
            answer++;
    }while (next_permutation(s.begin(), s.end()));
    return answer;
}

초기 스트링 s = ACFJMNRT라고 선언한 뒤, next_permutation을 통해 8!개의 경우의 수를 확인한다.

최악의 경우 40320 * 100 번의 탐색을 하게되어 시간초과는 발생하지 않게 된다.

 

만약 문자의 위치를 계속 linear하게 탐색하게 된다면 시간이 더 오래 걸리므로, map을 이용하여 해당 string의 index를 미리 저장해 놓는다. 

ex) s = "ACFJMNRT"일 때, N은 5, F는 2

 

index를 알고 있다면 그 사이에 몇 개의 문자가 올 수 있는지는 인덱스의 차이를 통해 구할 수 있으므로 위와 같이 구현하였다.