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

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제를 풀기 위해서는 시간복잡도를 빨리 눈치채는게 중요했다.

처음에 문제를 보고 어떻게 규칙을 찾아서 빠르게 계산을 할 수 있을까? 고민을 했다.

 

예를 들어 서로 연관된 규칙이 있는 경우에는 하나의 집합으로 포함시켜서 Combination을 계산하면 빠르게 조건을 탐색할 수 있지 않을까 생각했다.

 

하지만 아무리 생각해도 그 과정을 구현하기에는 힘들 것 같아서 다른 방법을 생각했다.

 

그러던 와중 8명을 배치하는 경우의 수가 8! 이고, 조건이 100개라는 걸 보고 둘을 곱하면 약 4,000,000 이므로 모든 경우를 직접 탐색해도 문제가 풀리겠다는 생각이 들었다.

 

그래서 8명을 배치하는 모든 경우의 수들 중 조건을 만족하는 경우를 찾아 +1을 해주도록 코드를 구현했다. 

 

순열만 만들면 조건에 부합하는지는 쉽게 구현할 수 있으므로 코드를 참고하면 된다.

 

 

​

[아이디어 정리]

1. 8명을 배치하는 모든 경우의 수를 만든다.
2. 각 경우의 수가 조건을 만족하는지 검사한다.
3. 만약 조건을 만족한다면 경우의 수를 1 더하고, 만족하지 않는다면 경우의 수를 1 뺀다.

 

 

Code

 

 

#include <string>
#include <vector>
#include <cmath>
using namespace std;


string str="ACFJMNRT";
int answer=0; // return 할 수 
bool visited[8];
char nv[8]; // 경우의 수

void Calc(vector<string> &data) //비교하는 함수
{
    char charSt,charEd,rela,Cnt;
    int dist, compDist;
    for (int i=0; i<data.size(); i++){
        charSt=data[i][0],charEd=data[i][2];
        dist = 0;
        compDist=data[i][4]-'0'; // 조건 거리
        
        for (int j=0; j<8; j++){
            if (nv[j]==charSt||nv[j]==charEd)
                dist=abs(dist-j);  // 두 인원 사이의 거리 계산   
        }
        dist-=1;
        
        //조건을 만족하지 않으면 종료
        if (data[i][3]=='='){
            if (dist!=compDist){
                return;
            }
        }
        else if (data[i][3]=='<'){
            if (dist>=compDist){
                return;
            }
        }
        else{
            if (dist<=compDist){
                return;
            }
        }
    }
    answer+=1; // 모든 조건을 만족하면 +1
}

void Permu(int depth, vector<string> &data){
    if (depth==8)
    {
        Calc(data);
    }
    for (int i=0; i<8; i++){
        if (!visited[i]){
            visited[i]=true;
            nv[depth]=str[i];
            Permu(depth+1, data);
            visited[i]=false;
        }
    }
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, vector<string> data) {
    answer=0; // 초기화
    for (int i=0; i<8; i++) visited[i]=false; //초기화
    // 완전 탐색해도 400만
    Permu(0,data);
    return answer;
}

 

---

처음에 문제를 봤을 때, 난이도에 비해 엄청 어렵다고 느꼈다.

하지만 완전 탐색을 해도 되겠다는 생각이 들자마자 빠르게 문제를 풀 수 있었다.

최근에 특정 알고리즘 자체에 익숙해져서 뇌가 굳어버렸나...?

 

프로그래머스