[C++] 5658번 [모의 SW 역량테스트] 보물상자 비밀번호

 

 

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

---

 

25/02/07

 

 

16진수 변환을 곁들인 귀찮은 구현문제다.

---

 

문제 접근 방식:

 

 

주어진 숫자들이 16진수로 주어진 수들이기 때문에, 16진수로 주어진 수를 10진수로 변경하는 함수를 구현하는 것이 핵심이다.

 

이 문제에서 유의할 점은, 범위가 int범위를 넘어갈 수도 있다는 점이다.

 

$N$이 최대 28까지이고, 그 말은 최악의 경우 FFFFFFF라는 16진수 수를 10진수로 변경해야하는 일이 있을 수 있다.

 

실제로 10진수로 변경해보면 int범위를 조금 넘어가기 때문에 long long으로 받아야 한다.(2억이랑 21억이랑 헷갈려서 잘못된 말을 적었습니다.)

 

"진법 변환"을 어떻게 구현하냐가 결국 이 문제의 핵심인데, 이건 백준에서도 그렇고 너무나도 잘 알려진 유형이다.

 

10진법의 경우 1의 자리, $10$의자리, $10^2$의자리, $10^3$의자리,... 이런 식으로 주어진다.

 

따라서 마찬가지로 16진법에서 맨 오른쪽 숫자는 1의 자리, 다음 숫자는 16의 자리, 그 다음 숫자는 $16^2$의 자리, ... 이런 식으로 주어진다.

 

이 자리수에 현재 숫자를 곱하면 이 자리수에 놓여진 숫자의 크기가 되는 것이다.

 

이것들을 모두 더한 것이 실제 숫자가 되므로, 다음과 같이 간단하게 진법 변환 코드를 구현할 수 있다.

 

ll to_ll(string S){
    int idx = S.size()-1;
    ll digit = 1, ret = 0, adi;
    while (idx >= 0){
        if ('0' <= S[idx] && S[idx] <= '9'){
            adi = digit*((ll)(S[idx]-'0'));
        }
        else{
            adi = digit*((ll)((S[idx]-'A')+10));
        }
        digit *= 16;
        ret += adi;
        idx--;
    }
    return ret;
}

---

아래는 내가 위의 접근 방식과 같이 작성한 C++ 코드이다. 더보기를 누르면 확인할 수 있다.

// SWEA5658 [모의 SW 역량테스트] 보물상자 비밀번호
// 구현
/*
접근 방법:
long long 범위 주의
*/
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long ll;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'

ll to_ll(string S){
    int idx = S.size()-1;
    ll digit = 1, ret = 0, adi;
    while (idx >= 0){
        if ('0' <= S[idx] && S[idx] <= '9'){
            adi = digit*((ll)(S[idx]-'0'));
        }
        else{
            adi = digit*((ll)((S[idx]-'A')+10));
        }
        digit *= 16;
        ret += adi;
        idx--;
    }
    return ret;
}

void solve(int test_case_num){
    int N, K; cin >> N >> K;
    string S; cin >> S;
    S = S+S;
    vector<ll> numbers;
    int len = N/4;
    for (int i = 0; i < len; i++){
        for (int j = 0; j < 4; j++){
            ll num = to_ll(S.substr(i+j*len, len));
            if (find(numbers.begin(), numbers.end(), num) == numbers.end()) numbers.push_back(num);
        }
    }
    sort(numbers.begin(), numbers.end(), greater<ll>());
    cout << '#' << test_case_num << ' ' << numbers[K-1] << endl;
    return;
}

int main(void){
    int T; cin >> T;
    for (int i = 1; i <= T; i++){
        solve(i);
    }
    return 0;
}