[프로그래머스] 단체사진찍기 / DFS, assign, next_permutation

문제

 

 

 

풀이

#include <string>
#include <vector>
#include <algorithm>
#include <memory.h>
#include <cstdlib> // abs
using namespace std;

int answer;
vector<char> names;
vector<bool> visited;
vector<string> conditions;
void dfs(int n, string inputstr);
bool check(string str);

int solution(int n, vector<string> data) {
    answer = 0;
    names = {'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'};
    visited.assign(8,false); // vector 초기화
    conditions = data;
    dfs(0, "");

    return answer;
}


bool check(string str){
    for(auto c : conditions){
        int idx1 = find(str.begin(), str.end(), c[0]) - str.begin();
        int idx2 = find(str.begin(), str.end(), c[2]) - str.begin();
        int len = abs(idx1 - idx2) -1;
        int hope = c[4] - '0';
        switch(c[3]){
            case '=':
                if(len != hope) return false;
                break;
            case '<': // 미만
                if(len >= hope) return false;
                break;
            case '>': // 초과
                if(len <= hope ) return false;
                break;
        }
    }
    return true;
}

void dfs(int n, string inputstr){
    if(n == 8){
        if(check(inputstr)) answer++;
        return;
    }
    
    //경우의 수 다 구하기    
    for (int i = 0; i < visited.size(); i++) {
        if(!visited[i]){
            string str = inputstr + names[i];
            visited[i] = true;
            dfs(n+1, str);
            visited[i] = false; // 숫자의 순서를 바꿔주기 위함
        }
    }
    
    return;
}

해결 과정

1. DFS를 사용하여 모든 경우의 수 구하기.(DFS, BFS를 사용한 완전 탐색으로 모든 경우의 수를 구할 수 있다!)

2. 문자열을 check함수를 사용하여 조건을 만족하는지 확인 후, 만족한다면 answer(count) 증가시키기.

 

DFS를 사용하여 모든 경우의 수를 다 구하는 원리는 밑 사이트를 참고하면 된다!

값이 중복되지 않도록 visited배열을 사용하였다. 

 

 

---

 

다른 사람 풀이

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

using namespace std;

inline int normalize_alphabet(char c)
{
    assert(c >= 'A' && c <= 'Z');
    return c - 'A';
}

inline int normalize_digit(char c)
{
    assert(c >= '0' && c <= '9');
    return c - '0';
}

inline int abs(int n)
{
    return n < 0 ? -n : n;
}

inline void get_indexes(int (*index)[26], const char* str)
{   
    for (int i = 0; str[i] != '\0'; i++)
    {
        (*index)[normalize_alphabet(str[i])] = i;
    }   
}

int solution(int n, vector<string> data)
{
    char str[] = "ACFJMNRT";
    int index[26] = { 0, };
    get_indexes(&index, str);

    int perm[] = {0,1,2,3,4,5,6,7};

    int answer = 0;
    do
    {
        bool flag = true;

        for (string& cond : data)
        {
            const int name1 = normalize_alphabet(cond[0]);
            const int name2 = normalize_alphabet(cond[2]);
            const int num = normalize_digit(cond[4]);
            const char op = cond[3];

            const int dist = abs(perm[index[name1]] - perm[index[name2]]) - 1;

            if (op == '>' && !(dist > num)) flag = false;
            if (op == '=' && !(dist == num)) flag = false;
            if (op == '<' && !(dist < num)) flag = false;

            if (flag == false)
            {
                break;
            }
        }
        if (flag)
        {
            answer++;
        }
    } while (next_permutation(perm, perm + 8));

    return answer;
}

next_permutation을 사용하여 모든 순열을 구할 수 있었다.

 

next_permutation

// default
bool next_permutation (BidirectionalIterator first,
                         BidirectionalIterator last);
 
// custom
bool next_permutation (BidirectionalIterator first,
                         BidirectionalIterator last, Compare comp);
//custom에서 볼 수 있듯이 비교 함수 comp를 인자로 넘기는 것도 가능하다.

- n개의 원소의 순열(permutation / 순서에 상관있게 값들을 나열하는 것)을 구하는 함수

- 인자로 반복자를 받기 때문에 vector 뿐만 아니라 string 타입의 변수도 순열을 구해낼 수 있다.

- 만약 해당 컨테이너에 다음 순열이 존재하면 그 컨테이너의 원소를 해당 순열 순서로 바꾸고 true를 반환한다

- 다음 순열이 없다면 false를 반환한다.

 

 

next_permutation의 주의할 점

- 오름차순으로 정렬된 값을 가진 컨테이너로만 원하는 값을 얻을 수 있다.

• default로 operator < 를 사용해 순열을 생성한다. 즉 오름차순으로 순열을 생성한다. 
• next_permutation은 더 큰 순열로 재배열을 할 수 있으면 반복하여 구해내는 구조이므로 앞에 이미 큰 원소들이 배치되어 있으면 반복하지 않게 된다.
• 만약 데이터가 내림차순으로 정렬이 되어 있다면 prev_permutation을 사용하면 된다.
• prev_permutation은 내림차순 정렬된 데이터를 받아서 이전 순열로 바꿔준다.

- 중복이 있는 원소들은 중복을 제외하고 순열을 만들어 준다. 

 

 

 

---

https://velog.io/@sds1vrk/DFS%EB%A5%BC-%ED%99%9C%EC%9A%A9%ED%95%9C-%EC%A4%91%EB%B3%B5%EC%88%9C%EC%97%B4-%EC%88%9C%EC%97%B4-%EC%A1%B0%ED%95%A9-%EA%B5%AC%ED%95%98%EA%B8%B0

DFS를 활용한 중복순열, 순열, 조합 구하기

https://mjmjmj98.tistory.com/38

[C++ / Algorithm] 순열(next_permutation) 사용 방법과 조합(Combination) 구하기