프로그래머스 - 단체사진 찍기

programmers.co.kr/learn/courses/30/lessons/1835

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

 

처음에 이문제를 풀때,

이게 레벨 2가 맞나 싶었다.

처음에 이것저것 많이 고려해야 된다고 생각했기 때문이다.

 

일단 먼저, 문제 설명에서 "네오는 프로도와 나란히 서기를 원했고, 튜브가 뿜은 불을 맞은 적이 있던 라이언은 튜브에게서 적어도 세 칸 이상 떨어져서 서기를 원했다" 를 보고 이 조건을 만족시키면서 동시에 문제에서 조건으로 주어지는 data 의 조건도 만족해야 된다고 생각했다.

세가지 조건을 모두 만족하는 브루트포스를 돌려야 된다고 생각했으나, 다른 사람들의 답을 보니 그렇지 않은것 같다

 

문제에서 글자가 8개중 하나라 했고, 이 8개 문자를 변수로 갖는 string order = "ACFJMNRT"; 를 만들어 줬다.

그리고 순열을 통해서 모든 경우의 수를 다 돌려봐야 하므로

next_permutation 을 써준다.

조건식 모음인 data 에서 문자열을 하나씩 빼주고, (string str : data)

이 문자열에서 첫번째 문자(조건을 제시한 프렌즈), 두번째 문자(첫번째 문자의 상대방), 연산자 기호(=, >, <), 거리를 나타내는 숫자값(str 의 마지막 char) 를 뽑아낸다.

현재 순열에서 첫번째 문자와 두번째 문자 사이에 존재하는 문자의 수 (즉, 문제에서 정의한 거리) 를 구하기 위해

string 의 find 함수를 활용하여 두 문자의 인덱스 차를 구하고, 음수가 나올 수 있으므로, 절대값을 갖는 별도의 변수를 만들어 처리한다 (1을 더 빼줘야 하는건 둘 사이의 문자 갯수만 알면 되기 때문이다)

 

이렇게 구한 값들을 토대로 조건에 부합하는지 확인을 하기 위해

is_valid() 라는 함수를 만들었고, 조건을 만족하면 다음 조건식으로 (data 의 다음번째 문자)

그렇지 않으면 조건식들(data 내부의 string 들) 사이에 문제가 있는 것이므로, 반복문을 나간다.

 

 

- c++

 

#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
 
using namespace std;
 
bool is_valid(char op, int num, int dist) {
    switch (op) {
        case '=':
            return dist == num;
            break;
        case '>':
            return dist > num;
            break;
        case '<':
            return dist < num;
            break;
    }
}
 
int solution(int n, vector<string> data) {
    int answer = 0;
    string order = "ACFJMNRT";
 
    do {
        bool flag = true;
        for (string str : data) {
            char first = str[0], second = str[2], op = str[3];
            int num = str[4] - '0', diff = order.find(first) - order.find(second);
            int dist = abs(diff) - 1;
 
            if (is_valid(op, num, dist)) continue;
            flag = false;
            break;
        }
        if (flag) answer++;
    } while (next_permutation(order.begin(), order.end()));
 
    return answer;
}