단체사진 찍기(2017 카카오코드 본선)

문제 링크

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

 

풀이

처음에 많이 고민했다.

재귀로 하면 비효율적 일지 하면서 찾아보았더니 재귀로도 풀린다고는 한다.

하지만 함수 하나로 끝내고 싶었기에 next_permutation() 함수를 사용하여 순열을 돌렸고 모든 조건을 검사하였다.

완전 탐색이다.

1. 자리를 배치한다.

2. sort한다.(오름차순- next_permutation(), 내림차순- prev_permutation())

3. do-while()문으로 조건 검사하며 개수를 증가시킨다.

 

#include <string>
#include <vector>
#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

bool condition(const int& n, const vector<string>& data, const string& locate)      // 조건 검사
{
    bool check = true;
    for(int i=0; i<n; i++)
    {
        char c1 = data[i][0];       // 첫 번째
        // 두 번째는 항상 '~' 이므로 Skip
        char c3 = data[i][2];       // 세 번째
        char c4 = data[i][3];       // 네 번째
        int c5 = data[i][4] - '0';  // 다섯 번째
        
        switch(c4)
        {
            case '=':{ check &= abs((int)locate.find(c1) - (int)locate.find(c3)) -1 == c5; }
                break;
            case '>':{ check &= abs((int)locate.find(c1) - (int)locate.find(c3)) -1 > c5; }
                break;
            case '<':{ check &= abs((int)locate.find(c1) - (int)locate.find(c3)) -1 < c5; }
                break;
        }
        if(!check){ break; }
    }
    return check;
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, vector<string> data) {
    int answer = 0;
    string locate = "ACFJMNRT";
    sort(locate.begin(), locate.end());
    
    do
    {
        if(condition(n, data, locate)) answer++;                // 조건 검사
    }
    while(next_permutation(locate.begin(), locate.end()));      // 자리 바꾸면서
    
    return answer;
}