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

문제

SWEA 모의 SW 역량테스트 - 5658 보물상자 비밀번호

SW Expert Academy

 

---

문제 풀이

접근 방식

주어진 문자열을 4등분하여 만들 수 있는 모든 16진수를 10진수로 바꿔 K번째로 큰 수를 구하는 문제이다.

 

문자열 한 칸씩 이동시키며 가능한 문자열을 모두 찾아주어야하기 때문에 아래와 같이 코드를 작성하였다.

아래의 코드에서 M은 문자열의 총 길이를 4로 나눈 값을 의미하며,

n에 M개의 문자를 넣고, 이를 DEC 함수를 이용하여 10진수의 값으로 바꿔 answer 벡터에 넣어주었다.

for (int i = 0; i < M; i++) {
	for (int j = 0; j < 4; j++) {
		n = "";
		for (int k = 0; k < M; k++) {
			n += num[((j * M) + k + i) % N];
		}
		answer.push_back(DEC(n));
	}
}

 

DEC 함수는 아래와 같이 구현하였다.

16진수는 숫자 뿐만 아니라, A~F까지의 알파벳도 포함되어 있기 때문에 이를 고려하여 코드를 작성하였다.

int DEC(string n) {
    int len = n.size();
    int result = 0;
    for (int i = 0; i < len; i++) {
        if(n[i] >= '0' && n[i] <= '9')
            result += (n[i] - '0') * pow(16, len - i - 1);
        else
            result += (n[i] - 'A' + 10) * pow(16, len - i - 1);
    }
    return result;
}

 

 

이 문제는 10진수로 바꾼 숫자들 중에서 중복을 제외하고 K번째로 큰 수를 찾는 문제이기 때문에

내림차순으로 정렬을 해주고 unique()로 중복된 숫자들을 뒤쪽으로 이동 시켜준 후,

아래의 코드와 같이 answer[K-1]을 답으로 출력해주었다.

sort(answer.begin(), answer.end(), greater<int>());
unique(answer.begin(), answer.end());

cout << "#" << test_case << " " << answer[K - 1] << endl;

 

---

풀이 코드 - C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <string>
#include <cmath>
using namespace std;
 
int DEC(string n) {
    int len = n.size();
    int result = 0;
    for (int i = 0; i < len; i++) {
        if(n[i] >= '0' && n[i] <= '9')
            result += (n[i] - '0') * pow(16, len - i - 1);
        else
            result += (n[i] - 'A' + 10) * pow(16, len - i - 1);
    }
    return result;
}
 
int main(int argc, char** argv) {
    int test_case;
    int T, N, K, M;
    string n;
    cin >> T;
    for (test_case = 1; test_case <= T; ++test_case) {
        cin >> N >> K;
        M = N / 4;
        vector<char> num(N);
        vector<int> answer;
 
        for (int i = 0; i < N; i++)  {
            cin >> num[i];
        }
 
        for (int i = 0; i < M; i++)  {
            for (int j = 0; j < 4; j++)  {
                n = "";
                for (int k = 0; k < M; k++)  {
                    n += num[((j * M) + k + i) % N];
                }
                answer.push_back(DEC(n));
            }
        }
        sort(answer.begin(), answer.end(), greater<int>());
        unique(answer.begin(), answer.end());
 
        cout << "#" << test_case << " " << answer[K - 1] << endl;
    }
    return 0;
}

실행 결과