[프로그래머스] C/C++ [2017 카카오코드 본선] 단체사진찍기

https://programmers.co.kr/learn/courses/30/lessons/1835?language=cpp 

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

 

풀이

처음에는 수학문제인가 싶어서 공식을 찾으려 해봤지만 잘 찾기 어려웠다. 그래서 완탐을 해야하나 싶어서 시간복잡도를 계산해보니 8개 모두를 순열을 돌리므로 8! = 40320 *100(조건) = 4032000 약 400만밖에 안되므로 여유로웠다!😳

그래서 완탐을 돌리고 조건에 맞는것만 찾아서 카운트하는 방식으로 풀었다.

 

소스코드

#include <iostream>
#include <string>
#include <vector>

using namespace std;
int visited[8];
string line;

string people;
int answer;
int cnt;

bool isOk(vector<string> data){
    
    for(int i=0; i<data.size(); i++){
        
        char left = data[i][0];
        char right = data[i][2];
        int dist = data[i][4] - '0';
        dist++;
        int left_index, right_index;
        
        for(int i=0; i<line.size(); i++){
            if(line[i] == left){
                left_index = i;
            }
            if(line[i] == right){
                right_index = i;
            }
        }
        
        if(data[i][3] == '='){
            if(abs(left_index-right_index) != dist){
                
                return false;
            }
            continue;
        
        }
        else if(data[i][3] == '>'){
            
            if(abs(left_index-right_index) <= dist){
                return false;
            }
            continue;
        }
        else{
            if(abs(left_index-right_index) >= dist){
                return false;
            }
            continue;
        }
    }
    
    return true;
}

void makeCase(int cnt, vector<string> data){
    if(cnt == 8){
        if(isOk(data)){
            answer++;
        }
        return;
    }
    
    for(int i=0;i<8;i++){
        if(!visited[i]){
            line+=people[i];
            visited[i] = 1;
            makeCase(cnt+1, data);
            line.pop_back();
            visited[i]= 0;
            
        }
    }
}
int solution(int n, vector<string> data) {
    answer = 0;
    people = "ACFJMNRT";
   
    makeCase(0, data);
    return answer;
}

아 그리고 순열을 만들때 vector를 이용해서 만들면 시간초과가 걸린다. string을 이용하자!

(400만이라 여유로울줄알고 편한 vector로 했는데 시간초과가 나왔다.. push_back이 시간을 많이 잡아먹는 것 같다..!)😒

테스트가 1개 뿐이넹🤫