단체사진 찍기(47분)

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

구현 아이디어 2분 구현 45분

풀이

처음에 ch배열 하나만 가지고 뭔가 하려고 하다가... 정신 차려니 40분이 지나있어서 그냥 배열 하나 더 해서 풀었다. DFS를 그래도 제일 많이 풀어봤는데 47분이라니 처참하다!

8명이 서는 경우의 수를 구해 조건과 비교했다.

#include <string>
#include <vector>

using namespace std;
char ch[8], comb[8], name[8];
int answer;

void DFS(int L, const vector<string>& data)
{
    if(L == 8)
    {
        // 데이터 확인.
        bool correct = true;
        for(int i = 0; i < data.size(); ++i)
        {
            string d = data[i];
            char c1 = data[i][0];
            char c2 = data[i][2];
            char c3 = data[i][3];
            char c4 = data[i][4];
            
            int idx1, idx2;
            for(int i = 0; i < 8; ++i)
            {
                if(comb[i] == c1) idx1 = i;
                if(comb[i] == c2) idx2 = i;
            }
            
            if(c3 == '=')
            {
                if(abs(idx1 - idx2) != c4 - '0' + 1)
                {
                    correct = false;
                    break;
                }
            }
            else if(c3 == '<')
            {
                if(abs(idx1 - idx2) > c4 - '0')
                {
                    correct = false;
                    break;
                }
            }
            else
            {
                if(abs(idx1 - idx2) <= c4 - '0' + 1)
                {
                    correct = false;
                    break;
                }
            }
        }
        
        if(correct) ++answer;
    }
    else
    {
        for(int i = 0; i < 8; ++i)
        {
            if(ch[i] == 0)
            {
                ch[i] = 1;
                comb[L] = name[i];
                DFS(L + 1, data);
                ch[i] = 0;
            }
        }
    }
}

int solution(int n, vector<string> data) {
    answer = 0;
    
    name[0] = 'A';
    name[1] = 'C';
    name[2] = 'F';
    name[3] = 'J';
    name[4] = 'M';
    name[5] = 'N';
    name[6] = 'R';
    name[7] = 'T';
    
    for(int i = 0; i < 8; ++i)
    {
        comb[i] = 0;
        ch[i] = 0;
    }

    DFS(0, data);
    
    return answer;
}

---

next_permutation

next_permutation의 존재를 알게 되었다! 써 봐야지!

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

using namespace std;

int main()
{
    vector<int> arr{ 0, 0, 1 };

	// 와! 정말 신기하다!
    do
    {
        for (auto it : arr)
            printf("%d ", it);
        printf("\n");
    } while (next_permutation(arr.begin(), arr.end()));

    return 0;
}

---

prev_permutation

prev_permutation을 활용해 조합 구하기까지 가능하다! 와!

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

using namespace std;

int main()
{
    vector<int> arr{ 1, 2, 3, 4 };
    vector<int> tmp{ 1, 1, 0, 0 };

    do
    {
        for (int i = 0; i < tmp.size(); ++i)
        {
            if (tmp[i] == 1)
                printf("%d ", arr[i]);
        }
        printf("\n");
    } while (prev_permutation(tmp.begin(), tmp.end()));

    return 0;
}

---

풀이(next_permutation)

next_permutation은 다음 순열을 구하는 함수이며 prev_permutation은 이전 순열을 구하는 함수이다. 활용한 풀이!

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

using namespace std;

int solution(int n, vector<string> data) {
    int answer = 0;
    
    string str = "ACFJMNRT";
    
    // next_permutation 함수를 써서 순열을 구할테다.
    vector<int> perm{0, 1, 2, 3, 4, 5, 6, 7};

    do
    {
        bool correct = true;
        
        for(auto d : data)
        {
            char name1 = d[0];
            char name2 = d[2];
            char op = d[3];
            int dist = d[4] - '0';
            
            int idx1 = 0, idx2 = 0;
            for(int i = 0; i < 8; ++i)
            {
                if(name1 == str[perm[i]]) idx1 = i;
                else if(name2 == str[perm[i]]) idx2 = i;
            }
            
            // 두 프렌즈 사이에 있는 다른 프렌즈의 수.
            int sub = abs(idx1 - idx2) - 1;
            
            if(op == '=' && !(sub == dist)) correct = false;
            else if(op == '<' && !(sub < dist)) correct = false;
            else if(op == '>' && !(sub > dist)) correct = false;
            
            if(!correct) break;
        }
        
        if(correct) ++answer;
        
    }while(next_permutation(perm.begin(), perm.end()));

    return answer;
}

---

와!