해당 문제는 dfs를 이용한 순열 구하기로 해결하였다. 8명의 프렌즈를 나열하는 모든 경우의 수를 만들고 조건과 비교하는 방식이다. 때문에 실행 시간이 매우 오래 걸리는 문제이다. 물론 논리에 맞게 잘 처리해주면 조건을 먼저 세워두고 그에 맞게 경우의 수를 계산할 수 있겠지만.. 우리는 사용할 시스템을 만드는 게 아니라 코딩 테스트에서 빠르게 사용할 수 있는 알고리즘을 공부하는 것이므로..
각설하고, 바로 코드를 살펴보자. 이번 코드는 총 세 개의 함수로 분리하여 작성하였다.
#include <string>
#include <vector>
#define MAX_SIZE 8
int arr[MAX_SIZE], visit[MAX_SIZE], perm[MAX_SIZE];
std::vector<std::string> conditions;
int condition_cnt;
int correct;전역으로 선언한 변수들이다. 각각
arr: 프렌즈 목록visit: 순열에 해당 프렌드가 이미 포함되었는지 여부perm: 실제 프렌즈가 나열된 순열conditions: 다른 함수들에서 조건(solution()함수에 전달된data매개변수)을 쉽게 가져다 사용할 수 있게 하는 벡터condition_cnt: 특정 순열이 만족하는 조건의 수correct: 모든 조건을 만족하는 순열의 수
를 의미한다.
bool check(std::string condition) { // condition = 조건 문자열(ex. "N~F=0")
// condition[0] : 1st friend, [1] : ~, [2] : 2nd friend, [3] : inequality, [4] offset
int first;
int second;
for (int count = 0; count < MAX_SIZE; count++) {
if (perm[count] == condition[0]) {
first = count;
}
if (perm[count] == condition[2]) {
second = count;
}
}
int diff = (first - second > 0) ? first - second + 47 : second - first + 47;
switch (condition[3]) {
case '=':
if (diff == condition[4])
return true;
return false;
case '<':
if (diff < condition[4])
return true;
return false;
break;
case '>':
if (diff > condition[4])
return true;
return false;
}
}만들어진 수열이 조건을 만족하는지 판단하는 함수이다. 각 프렌즈가 몇 번째에 위치하는지 찾고 그 간격(diff)이 몇인지 계산한다. 차이를 항상 양수로 만들기 위해 삼항 연산자로 처리해주었다.
diff를 구하는 수식이 조금 의아할 수 있는데, (첫 번째 프렌드의 위치 first) - (두 번째 프렌드의 위치 second) 이후에 오는 + 47은 - 1 + '0'을 의미하는 것이다. 프렌즈의 위치를 설정하는 조건 N~F=0에서 숫자 0은 실제 두 프렌즈의 거리 차가 아닌 '두 프렌즈 사이에 있는 다른 프렌즈의 수'이다. 따라서 거리(인덱스) 차에서 1을 빼주어 간격을 설정해주었다.
또한 condition이 문자열이기 때문에 조건 내의 숫자는 정수형 0이 아닌 문자형 '0'이다. 이를 정수형으로 계산해주기 위해 - '0'을 해줘 결과적으로 + 47이라는 연산이 추가된 것이다.
void perm_dfs(int cnt) {
if (cnt == MAX_SIZE) {
int correct_cnt = 0;
for (auto condition : conditions) {
if (check(condition))
correct_cnt++;
}
if (correct_cnt == condition_cnt) {
correct++;
}
}
else {
for (int index = 0; index < MAX_SIZE; index++) {
if (!visit[index]) {
perm[cnt] = arr[index];
visit[index] = 1;
perm_dfs(cnt + 1);
visit[index] = 0;
}
}
}
}실제 순열을 만드는 dfs 함수이다. dfs 로직 자체는 동일하고, 프렌즈가 새롭게 나열되었을 때 나열된 결과가 조건을 만족하는지 판단하고 카운팅을 해주었다.
int solution(int n, std::vector<std::string> data) {
int answer = 0;
correct = 0;
condition_cnt = n;
conditions.clear();
for (int index = 0; index < MAX_SIZE; index++) {
arr[index] = 0;
visit[index] = 0;
perm[index] = 0;
}
for (auto condition : data) {
conditions.push_back(condition);
}
arr[0] = 'A';
arr[1] = 'C';
arr[2] = 'F';
arr[3] = 'J';
arr[4] = 'M';
arr[5] = 'N';
arr[6] = 'R';
arr[7] = 'T';
perm_dfs(0);
return correct;
}solution() 함수부는 매우 간단하다. 그냥 변수들을 초기화해주고 dfs 결과를 반환하는 것이 전부이다.
이를 코드가 상당히 긴데, dfs로 순열을 만드는 것을 <algorithm> 헤더에서 제공하는 next_permutation() 함수로 대체하고 check() 함수의 switch 문을 if 문으로 바꿔주면 조금 더 단순한 코드가 만들어진다.
아래는 위의 코드 블럭을 합친 코드 전체와 next_permutation() 및 if 문을 이용해 간소화시킨 코드이다.
// Original version
#include <string>
#include <vector>
#define MAX_SIZE 8
int arr[MAX_SIZE], visit[MAX_SIZE], perm[MAX_SIZE];
std::vector<std::string> conditions;
int condition_cnt;
int correct;
bool check(std::string condition) {
int first;
int second;
for (int count = 0; count < MAX_SIZE; count++) {
if (perm[count] == condition[0]) {
first = count;
}
if (perm[count] == condition[2]) {
second = count;
}
}
int diff = (first - second > 0) ? first - second + 47 : second - first + 47;
switch (condition[3]) {
case '=':
if (diff == condition[4])
return true;
return false;
case '<':
if (diff < condition[4])
return true;
return false;
break;
case '>':
if (diff > condition[4])
return true;
return false;
}
}
void perm_dfs(int cnt) {
if (cnt == MAX_SIZE) {
int correct_cnt = 0;
for (auto condition : conditions) {
if (check(condition))
correct_cnt++;
}
if (correct_cnt == condition_cnt) {
correct++;
}
}
else {
for (int index = 0; index < MAX_SIZE; index++) {
if (!visit[index]) {
perm[cnt] = arr[index];
visit[index] = 1;
perm_dfs(cnt + 1);
visit[index] = 0;
}
}
}
}
int solution(int n, std::vector<std::string> data) {
int answer = 0;
correct = 0;
condition_cnt = n;
conditions.clear();
for (int index = 0; index < MAX_SIZE; index++) {
arr[index] = 0;
visit[index] = 0;
perm[index] = 0;
}
for (auto condition : data) {
conditions.push_back(condition);
}
arr[0] = 'A';
arr[1] = 'C';
arr[2] = 'F';
arr[3] = 'J';
arr[4] = 'M';
arr[5] = 'N';
arr[6] = 'R';
arr[7] = 'T';
perm_dfs(0);
return correct;
}// Short version
#include <string>
#include <vector>
#include <algorithm>
#define MAX_SIZE 8
int arr[MAX_SIZE], visit[MAX_SIZE];
std::vector<std::string> conditions;
int condition_cnt;
int correct;
bool check(std::string condition) {
int first;
int second;
for (int count = 0; count < MAX_SIZE; count++) {
if (arr[count] == condition[0]) {
first = count;
}
if (arr[count] == condition[2]) {
second = count;
}
}
int diff = (first - second > 0) ? first - second + 47 : second - first + 47;
if (condition[3] == '=') {
return diff == condition[4];
}
else if (condition[3] == '>') {
return diff > condition[4];
}
else if (condition[3] == '<') {
return diff < condition[4];
}
}
int solution(int n, std::vector<std::string> data) {
int answer = 0;
correct = 0;
condition_cnt = n;
conditions.clear();
for (int index = 0; index < MAX_SIZE; index++) {
visit[index] = 0;
}
for (auto condition : data) {
conditions.push_back(condition);
}
arr[0] = 'A';
arr[1] = 'C';
arr[2] = 'F';
arr[3] = 'J';
arr[4] = 'M';
arr[5] = 'N';
arr[6] = 'R';
arr[7] = 'T';
do {
int correct_cnt = 0;
for (auto condition : conditions) {
if (check(condition))
correct_cnt++;
}
if (correct_cnt == condition_cnt) {
correct++;
}
} while (std::next_permutation(arr, arr + MAX_SIZE));
return correct;
}기본적으로 많은 구현체들이 switch 문을 점프 테이블로 구현하기 때문에 if / else if 가 3개 이상일 땐 되도록 switch 문으로 작성하는 것이 성능에 좋다는 이야기가 있다. 하지만 이것이 실제 시스템에 드라마틱한 변화를 가져다주진 않기 때문에 큰 상관은 없어 보인다.
또한 stl에서 제공하는 next_permutation() 함수가 성능적으로 좋지 않다는 이야기도 있었지만, 이번 문제에서 테스트를 해본 결과 직접 dfs로 순열을 구하는 것과 큰 차이가 있어 보이지 않았다. 따라서 코딩 테스트에서 순열을 구할 땐 next_permutation() 함수를 애용하도록 하자.
