단체사진 찍기 C++
예제 입출력
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;
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, vector<string> data) {
int answer = 0;
string kakao ="ACFJMNRT";
do{
bool flag = true;
for(int i=0; i<n; i++)//제한사항 갯수
{
char first = data[i][0]; char second = data[i][2];
char compare = data[i][3]; int amount = data[i][4]-'0';
int tmp = kakao.find(second)-kakao.find(first);
int distance = abs(tmp) - 1;
if(compare == '=')//붙어있는 경우
{
if(distance == amount)flag = true;
else flag = false;
}
else if(compare == '<')
{
if(distance < amount)flag = true;
else flag = false;
}
else if(compare == '>')
{
if(distance > amount)flag = true;
else flag = false;
}
if(flag)continue;
else
{
flag = false;
break;
}
}
if(flag)answer++;
}while(next_permutation(kakao.begin(), kakao.end()));
return answer;
}
=> 사진을 찍을 수 있는 경우의 수는 '순열'의 개수입니다.
=> 순열의 갯수는 C++ algorithm header에 포함된 next_permutation을 통해 구현할 수 있습니다.
=> 처음에는 해당 제한사항을 포함한 경우의 수를 구하려 하였으나, 생각을 바꿨습니다.
=> CONCEPT : "순열을 구하며 제한사항에 해당하는 경우만 answer의 개수를 올려주는 것"입니다.
=> 위의 CONCEPT을 따라 코딩을 하다 보면 위의 코드와 같이 작성하게 됩니다.
=> find 함수를 통해 내가 찾는 녀석이 어디에 위치한 지 알아내고 둘의 거리를 구해야 합니다. (절댓값 필수)
=> 주어진 기호에 따라 주어진 녀석들의 거리가 제한사항과 맞닿아있는지 확인하며 bool값을 확인합니다.
=> 맞는 경우에만 answer의 값을 증가시켜주면 됩니다.
*최대한 IDE를 안 써야 하는데 계속 쓰게 됩니다... ㅠㅠ