[ SWEA 5658 ] 보물상자 비밀번호 (C++)

SWExpertAcademy의 보물상자 비밀번호(5658) 문제이다.

[ 문제풀이 ]

1) 가장 먼저 본인은 벡터배열을 이용해서 각 변에 들어가 있는 값들을 따로 입력으로 받아주었다.

   문제에서 주어지는 입력 'N'값은 전체 숫자의 길이를 나타낸다. 이 N값은 4의 배수이기 때문에 4로 나누게 되면

   한 변에 들어가는 숫자들의 갯수를 알 수 있다. 예를 들어서 N이 16이라면, 4개의 숫자들이 한변에 들어가게 되고

   총 4개의 변에 들어가지기 때문에 16개가 되는 것이다.

   그렇다면 보물상자에서 K번째로 큰 값을 구하기 위해서는 보물상자를 몇 번 시계방향으로 돌려보면 될까 ??

   바로, 한 변에 들어가 있는 숫자의 갯수만큼만 돌려보면 된다.

   왜 ?? 그 이상 돌려봤자 똑같은 숫자들만 반복해서 나오기 때문이다. 아래와 같은 예시를 한번 봐보자.

  

    가장 왼쪽 위의 그림부터 화살표 순서대로 1, 2, 3, 4번 그림이라고 가정해보면

    1번 상태에서 나올 수 있는 숫자 = { 123, 456, 987, CBA }

    2번 상태에서 나올 수 있는 숫자 = { A123, 345, 698, 87C }

    3번 상태에서 나올 수 있는 숫자 = { BA1, 234, 569, 87C }

    4번 상태에서 나올 수 있는 숫자 = { CBA, 123, 456, 987 }

    이렇게 존재한다. 그런데 ! 1번과 4번 상태를 확인해보자. 모두 동일한 숫자들로만 이루어져 있다.

    즉 ! 한 변에 들어가 있는 숫자가 3개이기 때문에, 최대 3번까지만 돌리는 것이 의미가 있고 그 이상은 의미가 없게된다.

    정리를 해보자면 우리는 보물상자를 "최대, 한 변에 들어있는 숫자의 갯수만큼" 만 회전 시켜 보면 된다.

2) 풀이를 실로 이게 끝이다. 본인은, 각 상태에서 나올 수 있는 숫자들을 저장하는 Vector를 만들어 주었고 중복 처리를 통해서

   중복된 값은 저장해 주지 않았다.

   또한, 반드시 16진수를 10진수로 변환하는 과정도 필요하다는 것 까먹지 말자 !

[ 소스코드 ]

#include<iostream>
#include<cstring>
#include<string>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int N, K, Line_Num, Answer;
vector<char> V[4];
vector<int> Result;
 
void Initialize()
{
    for (int i = 0; i < 4; i++)
    {
        V[i].clear();
    }
    Result.clear();
    Answer = 0;
 
}
 
void Input()
{
    cin >> N >> K;
    string Inp;
    cin >> Inp;
    Line_Num = N / 4;        // 한 변에 들어갈 수 있는 숫자의 갯수 파악
    int Idx = 0;            
    int Cnt = 0;
 
    for (int i = 0; i < Inp.size(); i++)
    {
        char Tmp = Inp[i];
 
        V[Idx].push_back(Tmp);    // 벡터 배열에 한 변에 들어갈 수 있는 숫자의 갯수만큼만 push.
        Cnt++;
        if (Cnt == Line_Num)
        {
            Idx++;
            Cnt = 0;
        }
    }
}
 
void Turning()
{
    /* 보물 상자를 시계 방향으로 회전시켜 보는 함수. */
    char Start = V[0].at(0);
    char Tail = V[3].at(Line_Num - 1);
 
    /* 회전시키는 방법
       - 첫 번째 변의 첫 번째 값과 마지막 값까지 계속해서 Swap ! 
       - 결과적으로 한 칸씩 회전 시킨것과 같은 효과.
    */
    for (int i = 0; i < 4; i++)
    {
        for (int j = 0; j < Line_Num; j++)
        {
            swap(V[0].at(0) , V[i].at(j));
        }
    }
    V[0].at(0) = Tail;
}
 
bool Find_Data(int d)
{
    for (int i = 0; i < Result.size(); i++)
    {
        if (Result[i] == d) return true;
    }
    return false;
}
 
void Calculate_Value()
{
    /* 16진수를 10진수로 변환 및 각 변에 있는 값들을 계산해서 Vector에 저장해 주는 함수. */
    for (int i = 0; i < 4; i++)
    {
        /* 16진수를 10진수로 변환하는 과정 */
        int p = Line_Num - 1;    
        int Sum = 0;
        for (int j = 0; j < V[i].size(); j++)
        {
            char c = V[i].at(j);
            int Tmp;
            if ('0' <= c && c <= '9') Tmp = c - '0';
            else if ('A' <= c && c <= 'F') Tmp = (c - 'A') + 10;
 
            int Sixteen = 1;
 
            for (int k = 0; k < p; k++) Sixteen = Sixteen * 16;
            
            Sum = Sum + Sixteen * Tmp;
            p--;
        }
         
        /* 중복된 값이 없으면 나올 수 있는 숫자들을 Vector에 저장. */
        if (Find_Data(Sum) == false) Result.push_back(Sum);
    }
}
 
bool desc(int a, int b) { return a > b; }
 
void Solution()
{
    /* 보물 상자의 초기 상태에서의 값들부터 모두 Check. */
    Calculate_Value();    
 
    for (int i = 0; i < Line_Num; i++)
    {
        Turning();
        Calculate_Value();
    }
 
    sort(Result.begin(), Result.end(), desc);
    Answer = Result[K - 1];
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << "\n";
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}