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

 

코딩으로 순열 조합에 대해서 카운트 해주는 문제를 접해본 적이 없었다. 손으로 풀어봤는데 이거를 어떻게 조건을 하나 하나 체크하지 라는 생각 뿐이었고, 해결할 방법을 몰랐다. 결국 구글링으로 다른 사람의 답안을 보면서 공부했다.

 next_permutation을 이용해서 오름차순에서 내림차순까지의 모든 순열 조합을 고려할 수 있었다. do while 문을 통해서 조건이 없는 모든 경우의 수를 구할 수 있었고 원하는 조건을 flag를 통해서 카운트할 지 말지를 결정해야 하는 알고리즘이었다.

 

 

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

using namespace std;

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, vector<string> data) {
    int answer = 0;
    
    // next_permutation 순열을 사용하기 위해서 오름차순으로 배열을 설정한다.
    string friends = "ACFJMNRT";
    
    do {
        bool flag = true;
        
        // 총 n개의 조건을 모두 탐색해야 한다.
        for(int i = 0 ; i < n ; i++) {
            int friend1_idx = 0;
            int friend2_idx = 0;
            
            // 순열의 배열 중 조건에 해당하는 Member의 index값을 찾아야 한다.
            for(int j = 0 ; j < friends.size() ; j++) {
                if(friends[j] == data[i][0])
                    friend1_idx = j;
                if(friends[j] == data[i][2])
                    friend2_idx = j;
            }
            
            // gap 변수에 조건에 해당하는 멤버들이 얼마나 떨어져있는지 계산해준다.
            int gap = max(friend1_idx-friend2_idx, friend2_idx-friend1_idx)-1;
            
            // 만약 = 표시가 있고 gap이 조건에 부합하지 않는다면 flag를 false 해준다.
            if(data[i][3] == '=') {
                if(gap != data[i][4] - '0') {
                    flag = false;
                    break;
                }
            }
    
            // 만약 > 표시가 있고 gap이 조건에 부합하지 않는다면 flag를 false 해준다.
            else if(data[i][3] == '>') {
                if(gap <= data[i][4] - '0') {
                    flag = false;
                    break;
                }
            }
            
            // 만약 < 표시가 있고 gap이 조건에 부합하지 않는다면 flag를 false 해준다.
            else if(data[i][3] == '<') {
                if(gap >= data[i][4] - '0') {
                    flag = false;
                    break;
                }
            }
        }
        
        // break로 탈출했건 안했건 flag의 T/F 유무에 따라 answer를 증가시킨다.
        if(flag == true) answer++;
        
    } while(next_permutation(friends.begin(), friends.end()));
    
    
    return answer;
}