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

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

코딩테스트 연습 - 단체사진 찍기

 

문제

 

해설

경우의 수를 계산하는 방법이 잘 떠오르지 않아 애먹었는데, 이 문제에서는 프렌즈 8명, n의 값이 최대 100으로 최대로 나오는 경우의 수가 8! * 100 = 4,032,000 이므로 그렇게 크지 않다. 따라서 프렌즈가 이룰 수 있는 모든 수열의 경우의 수를 확인하여 조건에 맞는지 체크하는 방법을 사용하면 된다!

 

🎈Key Point🎈

next_permutation 사용!

 

[전체 코드]

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int n, vector<string> data) {
    int answer = 0;
    string friends = "ACFJMNRT";

    do {
        bool flag = true;
        for (int i = 0; i < n; i++) {
            int idx1 = 0, idx2 = 0;

            for (int j = 0; j < friends.size(); j++) {
                if (data[i][0] == friends[j]) idx1 = j;
                if (data[i][2] == friends[j]) idx2 = j;
            }

            int gap = data[i][4] - '0';	
            int len = abs(idx1 - idx2) - 1;	

            if (data[i][3] == '=') {
                if (len == gap) continue;
                else {
                    flag = false;
                    break;
                }
            }
            else if (data[i][3] == '>') {
                if (len > gap) continue;
                else {
                    flag = false;
                    break;
                }
            }
            else {
                if (len < gap) continue;
                else {
                    flag = false;
                    break;
                }
            }
        }

        if (flag == true) answer++;

    } while (next_permutation(friends.begin(), friends.end()));

    return answer;
}