[프로그래머스] 코딩테스트 연습 2017 카카오코드 본선 단체사진 찍기 with C++(brute force)

안녕하세요! 오늘은 프로그래머스 단체사진 찍기 문제를 풀어보겠습니다.

 

이 문제는 제 기준에선 참 문제를 이해하기 어렵게 만들었다고 생각했는데요.

 

왜냐면 일렬로 선다고 해놓고 나란히 선다고 하고 저는 전체 경우의 수가 시그마n=1to8 8P(8-n)*n^(8-n)개인줄 알았습니다... 그래서 레벨2에도 엄청난 수열문제가 나올 수 있구나... 이런 마음이였는데요

 

다행히 그건아니고 최대 8!개를 탐색하는 문제였습니다!

 

또, 맞왜틀(맞는데 왜 틀리지?!) 문제입니다!

 

한 session에 하나의 testcase가 아니라 여러 testcase가 들어있어 전역 변수를 초기화 해주지 않으면 오답이 됩니다!

 

모두 구현한 뒤 오답이길레 한참 헤맸습니다 ㅠㅠ

 

잡설은 이쯤하고! 같이 문제 풀어보시죠!

 

 

 

알고리즘은 brute force입니다! 그냥 모든 경우의 수를 다 확인하겠다는 뜻이죠!

 

왜냐면 최종 경우의 수가 40000개이고 조건식이 많아야 1000개니 40,000,000번 연산에 끝난다는 뜻이죠?

 

컴퓨터에겐 얼마 안되는 횟수입니다!

 

그래서 dfs(경우의 수를 만들어주는 알고리즘으로 쓰입니다!)로 모든 경우의 수를 탐색하면서 만들어둔 condition을 확인하면 됩니다!

 

그때 그때 vector data를 참조하여 조건을 check해도 좋지만 struct로 만들어서 미리 정리해두고 쓰는 방법도 좋은듯하니 참고해서 보시면 됩니다!

 

 

#include <string>
#include <vector>

using namespace std;

#define	abs(x) (((x)>0)?(x):-(x))

int isUsingKakaoCharacter[8] = {0, 0, 0, 0, 0, 0, 0, 0};
char kakaoCharacter[8] = {'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'};
int conditionCount = 0;
int pictureCase[8] = {-1, -1, -1, -1, -1, -1, -1, -1};
int result = 0;

struct condition{
    int subject;
    int object;
    int distance;
    char distanceOperator;
};
condition conditionSet[100] = {0,};

int conditionCheck(){
    for(int i = 0; i < conditionCount; i++){
        int subjectPosition = 0;
        int objectPosition = 0;
        for (int j = 0; j < 8; j++) {
            if(conditionSet[i].subject == pictureCase[j]){
                subjectPosition = j;
            }
            if(conditionSet[i].object == pictureCase[j]){
                objectPosition = j;
            }
        }
        
        switch (conditionSet[i].distanceOperator) {
            case '>':
                if (abs(subjectPosition - objectPosition) <=  conditionSet[i].distance){
                    return 0;
                }
                break;
            case '<':
                if (abs(subjectPosition - objectPosition) >= conditionSet[i].distance){
                    return 0;
                }
                break;
            case '=':
                if (abs(subjectPosition - objectPosition) != conditionSet[i].distance){
                    return 0;
                }
                break;
            default:
                break;
        }
    }
    return 1;
}

void dfs(int depth){
    if(depth == 8){
        if (conditionCheck() == 1) result++;
        return;
    }

    for(int i = 0; i < 8; i++){
        if(isUsingKakaoCharacter[i] == 0){
            isUsingKakaoCharacter[i] = 1;
            pictureCase[depth] = i;
            depth++;
            dfs(depth);
            depth--;
            isUsingKakaoCharacter[i] = 0;
            pictureCase[depth] = -1;
        }
    }
}

int solution(int n, vector<string> data) {
    conditionCount = n;
    result = 0;
    
    for(int i = 0; i < n; i++) {
        for (int j = 0; j < 8; j++) {
            if(data[i].at(0) == kakaoCharacter[j]){
                conditionSet[i].subject = j;
            }
            if(data[i].at(2) == kakaoCharacter[j]){
                conditionSet[i].object = j;
            }
        }
        conditionSet[i].distanceOperator = data[i].at(3);
        conditionSet[i].distance = data[i].at(4) - '0' + 1;
    }
    
    dfs(0);
    
    return result;
}

 

오늘은 여기까지입니다!

 

좋은 하루 되세요!