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

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRUN9KfZ8DFAUo 

SW Expert Academy

<풀이>

1. 보물상자에 적힌 숫자를 입력받는다.

2. 보물상자에 적힌 숫자로 만들 수 있는 모든 수 중, K번째로 큰 수를 구하고 출력한다.

 

<해법>

1. 숫자를 만드는 방법

=> 슬라이딩 윈도우 알고리즘을 이용합니다. index를 편하게 관리하기 위해서, 뚜껑 문자열을 두 개 연달아 이어붙입니다.

 

#include <iostream>
#include <set>
 
using namespace std;
 
//16진수를 10진수로 바꾸는 함수
long long convertHexToDec(string str) {
    long long output = 0;
    for (int i = 0; i < str.length(); i++) {
        if (str[i] >= 'A' && str[i] <= 'F') {
            output = output * 16 + str[i] - 'A' + 10;
        }
        else {
            output = output * 16 + str[i] - '0';
        }
    }
    return output;
}
 
int main() {
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        int N = 0, K = 0;
        string cover = "";
        set<string, greater<>> s;
        long long answer = 0;
 
        //입력
        cin >> N >> K;
        cin >> cover;
 
        /* 해법 */
        //1. 가능한 모든 비밀번호를 set에 담음(슬라이딩 윈도우 이용)
        int passwordLength = N / 4;
        cover += cover;
        for (int i = 0; i < N; i++) {
            s.insert(cover.substr(i, passwordLength));
        }
 
        //2. K번째 수 저장
        int count = 1;
        for (string password : s) {
            if (count == K) {
                answer = convertHexToDec(password);
                break;
            }
            count++;
        }
 
        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }
 
    //종료
    return 0;
}

 

슬라이딩 윈도우와 구현에 대해 알아볼 수 있는 문제였습니다.