[c++] 프로그래머스 :: 단체사진찍기 (문제 풀이, 코드, 카카오 본선 문제)

단체사진 찍기

문제

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

문제 설명

가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 그런데 각자가 원하는 배치가 모두 달라 어떤 순서로 설지 정하는데 시간이 오래 걸렸다. 네오는 프로도와 나란히 서기를 원했고, 튜브가 뿜은 불을 맞은 적이 있던 라이언은 튜브에게서 적어도 세 칸 이상 떨어져서 서기를 원했다. 사진을 찍고 나서 돌아오는 길에, 무지는 모두가 원하는 조건을 만족하면서도 다르게 서는 방법이 있지 않았을까 생각해보게 되었다. 각 프렌즈가 원하는 조건을 입력으로 받았을 때 모든 조건을 만족할 수 있도록 서는 경우의 수를 계산하는 프로그램을 작성해보자.

입력 형식

입력은 조건의 개수를 나타내는 정수 n과 n개의 원소로 구성된 문자열 배열 data로 주어진다. data의 원소는 각 프렌즈가 원하는 조건이 N~F=0과 같은 형태의 문자열로 구성되어 있다. 제한조건은 아래와 같다.

• 1 <= n <= 100

• data 의 원소는 다섯 글자로 구성된 문자열이다. 각 원소의 조건은 다음과 같다.

  • 첫 번째 글자와 세 번째 글자는 다음 8개 중 하나이다. {A, C, F, J, M, N, R, T} 각각 어피치, 콘, 프로도, 제이지, 무지, 네오, 라이언, 튜브를 의미한다. 첫 번째 글자는 조건을 제시한 프렌즈, 세 번째 글자는 상대방이다. 첫 번째 글자와 세 번째 글자는 항상 다르다.
  • 두 번째 글자는 항상 ~이다.
  • 네 번째 글자는 다음 3개 중 하나이다. {=, <, >} 각각 같음, 미만, 초과를 의미한다.
  • 다섯 번째 글자는 0 이상 6 이하의 정수의 문자형이며, 조건에 제시되는 간격을 의미한다. 이때 간격은 두 프렌즈 사이에 있는 다른 프렌즈의 수이다.

출력 형식

모든 조건을 만족하는 경우의 수를 리턴한다.

예제 입출력

n	data	answer
2	[N~F=0,R~T>2]	3648
2	[M~C<2,C~M>1]	0

예제에 대한 설명

첫 번째 예제는 문제에 설명된 바와 같이, 네오는 프로도와의 간격이 0이기를 원하고 라이언은 튜브와의 간격이 2보다 크기를 원하는 상황이다.

두 번째 예제는 무지가 콘과의 간격이 2보다 작기를 원하고, 반대로 콘은 무지와의 간격이 1보다 크기를 원하는 상황이다. 이는 동시에 만족할 수 없는 조건이므로 경우의 수는 0이다.

---

코드

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

using namespace std;

bool testCase(string arr, string data) {
    char a = data[0];
    char b = data[2];
    char c = data[3];
    int d = atoi(&data[4]);

    int a_idx; int b_idx;
    for (int i = 0; i<8; i++) {
        if (arr[i] == a) {
            a_idx = i;
            continue;
        }
        if (arr[i] == b)
            b_idx = i;
    }

    int dist = abs(a_idx - b_idx);
    switch (c) {
    case '=':
        if (dist!=d+1)
            return false;
        break;
    case '<':
        if (dist>=(d+1))
            return false;
        break;
    case '>':
        if (dist<=(d+1))
            return false;
        break;
    }
    return true;
}

int setCase(string arr, int num, vector<string>& data) {
    do {
        int flag = 0;
        for (int i = 0; i < data.size(); i++) {
            if (!testCase(arr, data[i])) { // 거짓
                flag = 1;
                break;
            }
        }
        if (flag) // 거짓이면 다음꺼
            continue;
        else // 적합하면 num+1
            num++;
    } while (next_permutation(&arr[0], &arr[8]));

    return num;
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, vector<string> data) {
    int answer = 0;
    string arr = "ACFJMNRT";
    vector<vector<char>> line;
    answer = setCase(arr, 0, data); // 8! = 40320
    return answer;
}

 

풀이

 문제에서 항상 8명이 줄을 서는 것으로 가정했기 때문에, 줄을 서는 경우의 수는 8!인 40320이다. data(조건)는 최대 100개 들어온다고 했기 때문에, 각 경우의 수 당 data를 다 검사해도 4032000(<10^6) 의 시간복잡도 밖에 들지 않는다.

 따라서, 모든 경우의 수를 next_permutation 함수로 살펴보면서 동시에 data에 적합한지 살펴보는 방법을 택하였다. 처음에는 next_permutation으로 모든 경우의 수를 따로 저장한 후, data를 체크해보려고 했지만 시간이 너무 오래걸렸다. 사실 문제에서는 경우를 모두 구하는 것이 아니라 경우의 수만을 요구하고 있으므로, string을 직접 넣기보다 조건에 맞는 데이터가 존재하면 숫자를 하나씩 올리는 식으로 구성했다.

 

채점 결과

굉장히 오래 걸린다.

 

다른 사람의 풀이

string으로 다루기 어려워서 그냥 index로 바꾸어서 int형으로 다루는 식으로 문제를 변형한 분들이 많았다.