[Level_2 / C++ / 카카오] 단체사진 찍기 (C++)

 

<next_permutation> 모든 경우의 수 정렬

<abs> 절댓값 반환

---

* abs(), next_permutation() 함수를 사용하였으니 해당 함수를 모를 시  링크 참고. 

 

 

ex)  "N~F=0", "R~T>2"

 

벡터 data에 해당 문자열이 저장되어 온다고 가정하자.  각 문자열의 의미를 살펴보면 

 

"N~F=0" -> N과 F 사이에 아무도 없다. 즉, N과 F는 이웃해있다.

 

"R~T>2" -> R과 T 사이에  2칸이 넘는다. 즉, R과 T사이에 3명 이상이 있다. 

 

다음 조건이 모두 만족해야 answer 값이 +1 증가한다. 

 

해당 문제는 이렇게 접근했다. 

 

먼저, ACFJMNRT 의 정렬해서 나올 수 있는 경우의 수를 next_permutaion 함수를 활용 하였다. 

 

모든 경우의 수를 정렬

 

위의 그림을 봤을 때 next_permutaion함수를 do..while() 문법을 활용한다면 다음과 같이 정렬됨을 알 수 있다.  

총 8개의 문자를 정렬하는 방법은 8! 가지이므로 시간 초과는 일어나지않는다. 

 

8명의 친구들이 순서가 정해질 때 마다 data 벡터의 문자열들에 저장되어있는 조건문을 하나하나 다 살펴보고 

모든 조건문이 다 통과가 되면 answer++ 코드를 짜주면 된다. 

 

그렇기때문에 data 벡터의 크기만큼 반복하면서 해당 문자열의 두명의 친구 이름과 연산자, 그리고 친구들과의 간격차이값을 저장하고 8명이 정렬된 v라는 벡터에서 친구 두명의 인덱스 정보를 저장한다. 

 

두개의 인덱스 값이 나오는데 각 인덱스값들의 차이값을 절대값을 두어서 얼만큼 차이나는지 저장한다. 

 

이때, 주의할 점은 서로 이웃하면 간격이 0이라고 생각하면 안된다. 

 

"N~F=0" 

여기서 0의 값에 +1 을 더하고 나서 비교를 해야한다. 

 

즉, "NFACJMRT" 정렬된 벡터에서 N의 인덱스는 0 , F의 인덱스는 1 이니까 차이는 1이다. 

 

그렇기 때문에 

 

"N~F=0"   의 조건에서 문자열의 마지막 숫자 +1 을 해서 비교를 해야한다. 

 

 

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

using namespace std;

int solution(int n, vector<string> data) {
    int answer = 0;
    vector <char> v = { 'A','C','F','J','M','N','R','T' };
    do {
        int index1 = 0;//첫번째 문자 위치 저장
        int index2 = 0;//두번째 문자 위치 저장
        for (int i = 0; i < n; i++) { //data 문자열 비교
            for (int j = 0; j < 8; j++) {
                if (data[i][0] == v[j])index1 = j;
                else if (data[i][2] == v[j])index2 = j;
            }
            char compare = data[i][3]; // '=' or '>' or '<' 저장
            int number = data[i][4] - '0'; //간격차이     
            if (compare == '='&& abs(index1 - index2) != number + 1) break;       
            else if (compare == '>'&& abs(index1 - index2) <= number + 1) break;            
            else if (compare == '<'&& abs(index1 - index2) >= number + 1) break;            
            if (i == n - 1)answer++;
        }
    } while (next_permutation(v.begin(), v.end()));//계속해서 정렬
    return answer;
}

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

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