c++ 의 next_permutation은 어떤 배열이나 container의 모~든 조합을 반환해주는 함수이다.

혹자는 스타크래프트 테란 종족의 스파이더 마인과 같은 존재라고 하는데...

아무튼 편리하다는 것에는 의심이 없다.

 

사용형식은 다음과 같다:

do{
	코드
}while (next_permutation(container.begin(), container.end());
// or while (next_permutation(arr, arr+8));

 

자, 이제 이것을 사용해서 문제를 풀어보자.

 

순서는 이렇다.

1. 조건을 파싱하여 어떤 string 벡터에 담는다.

2. next_permutation이 제공하는 조합 하나하나에 대해 조건이 모두 일치하는지 탐색한다.

    2.1 타겟 문자 사이의 거리를 구한다.

    2.2 '=', '>', '<' 기호에 따라 타겟 문자 사이의 거리(distance)와 기호 뒤에 붙는 숫자를 비교한다.

    2.3 조건이 일치하지 않으면 flag를 false로 바꾸고 break;

3. flag가 true인 경우만 answer++;

#include <bits/stdc++.h>

using namespace std;

char characters[8] = {'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'};


int getDistance(char char1, char char2)
{
    int index1;
    int index2;
    
    for (int i = 0 ; i < 8; i++)
    {
        if (characters[i] == char1)
            index1 = i;
        if (characters[i] == char2)
            index2 = i;
    }
    
    return abs(index2 - index1);
}

int solution(int n, vector<string> data) {
    int answer = 0;
    
    vector<string> v;
    
    for (int i = 0; i < n; i++)
    {
        string tempString = "";
        tempString += data[i][0];
        tempString += data[i][2];
        tempString += data[i][3];
        tempString += data[i][4];
        v.push_back(tempString);
    }
    
    do {
        bool flag = true;
        for (int i = 0; i < n; i++)
        {
            char char1 = v[i][0];
            char char2 = v[i][1];
            char condition = v[i][2];
            int target = (int)(v[i][3] - '0');
            int distance = getDistance(char1, char2);
            distance--;
            if (condition == '=')
            {
                if (distance != target)
                {
                    flag = false;
                    break;
                }
            }
            else if (condition == '>')
            {
                if (distance <= target)
                {
                    flag = false;
                    break;
                }
            }
            else // condition == '<'
            {
                if (distance >= target)
                {
                    flag = false;
                    break;
                }
            }
        }
        if (flag == true)
            answer++;
        
    } while (next_permutation(characters, characters + 8));
    
    return answer;
}
  • 네이버 블러그 공유하기
  • 네이버 밴드에 공유하기
  • 페이스북 공유하기
  • 카카오스토리 공유하기

댓글을 달아 주세요

">