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

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.


각 변에 다음과 같이 16진수 숫자(0~F)가 적혀 있는 보물상자가 있다.

보물 상자의 뚜껑은 시계방향으로 돌릴 수 있고, 한 번 돌릴 때마다 숫자가 시계방향으로 한 칸씩 회전한다.

 

각 변에는 동일한 개수의 숫자가 있고, 시계방향 순으로 높은 자리 숫자에 해당하며 하나의 수를 나타낸다.

예를 들어 [Fig.1]의 수는 1A3, B54, 8F9, D66이고, [Fig.2]의 수는 61A, 3B5, 48F, 9D6이다.

보물상자에는 자물쇠가 걸려있는데, 이 자물쇠의 비밀번호는 보물 상자에 적힌 숫자로 만들 수 있는 모든 수 중, K번째로 큰 수를 10진 수로 만든 수이다.

N개의 숫자가 입력으로 주어졌을 때, 보물상자의 비밀 번호를 출력하는 프로그램을 만들어보자.

(서로 다른 회전 횟수에서 동일한 수가 중복으로 생성될 수 있다. 크기 순서를 셀 때 같은 수를 중복으로 세지 않도록 주의한다.)

 

[제약 사항]
 

1. N은 4의 배수이고, 8이상 28이하의 정수이다. (8 ≤ N ≤ 28)       
2. N개의 숫자는 각각 0이상 F이하로 주어진다. (A~F는 알파벳 대문자로만 주어진다.)
3. K는 생성 가능한 수의 개수보다 크게 주어지지 않는다.

 

[예제]
 

아래와 같이 (1, B, 3, B, 3, B, 8, 1, F, 7, 5, E) 12개의 숫자가 주어지고 K가 10인 경우를 살펴보자.
 

 

이 경우에 생성 가능한 수는 각 회전 별로 다음과 같다.  

0회전 : 1B3, B3B, 81F, 75E
1회전 : E1B, 3B3, B81, F75
2회전 : 5E1, B3B, 3B8, 1F7
3회전 : 0회전과 동일

생성 가능한 수를 내림 차순으로 나열하면 다음과 같고, K(=10)번째로 큰 수는 503(=1F7)이다.
(B3B를 중복으로 세지 않도록 주의한다.)

F75, E1B, B81, B3B, 81F, 75E, 5E1, 3B8, 3B3, 1F7, 1B3

 

 

[입력]

가장 첫 줄에는 테스트 케이스의 개수 T가 주어지고, 그 아래로 각 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 숫자의 개수 N과 크기 순서 K가 주어 진다.

그 다음 줄에는 16진수 0~F 숫자가 공백 없이 N개 주어진다.

 

[출력]

출력의 각 줄은 '#t'로 시작하고, 공백을 한 칸 둔 다음 정답을 출력한다.

(t는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)

 

처음에 long long으로 받아도 되는지 알고 1번 테케만 맞게 풀었는데

2번 부터 overflow나서 string으로 다시 시작했다... 처음부터 string으로 시작 하세요;;

 

그리고 string으로 받고 hex로 치환하는게 내장함수가 어디 없을까 하고

열심히 찾아본 결과

 

https://controlworld.tistory.com/entry/HEX-String-%EC%9D%84-Integer-%EA%B0%92%EC%9C%BC%EB%A1%9C-%EB%B3%80%EA%B2%BD%ED%95%98%EB%8A%94-%EB%B0%A9%EB%B2%95

HEX String 을 Integer 값으로 변경하는 방법

여기에 잘 설명 해놓으셨다

저 함수 쓰면 hex를 string으로 쉽게 바꿀 수 있다.

근데 저기는 const char *이고 내가 쓰는 타입은 string이다. 이것 때문에 또 많이 헤맸는데

string뒤에 c_str()을 붙여주면 해결된다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
 
using namespace std;
 
int n,k,ans;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int tc;
    long long ans,k;
    cin>>tc;
    for(int t=1;t<=tc;t++)
   {
        ans = 0;
        cin>>n>>k;
        vector<long long>V(n,0);
        int div = n/4;
        string s;
        cin>>s;
        string tail = s.substr(s.length() - div + 1, div - 1);
        s = tail + s;
 
        while(s.length()>=div)
        {
            string temp = s.substr(0, div);
 
            long long number = (long long)strtol(temp.c_str(), NULL, 16);
 
            V.push_back(number);
            s = s.substr(1, s.length() - 1);
 
        }
        sort(V.begin(), V.end(), greater<long long>());
        int a = 0;
        long long start = V[0];
        for(int i=1;i<V.size();i++)
        {
            if(V[i]!=start)
            {
                start = V[i];
                a++;
            }
            if(a==k)
            {
                cout<<'#'<<t<<' '<<V[i - 1]<<'\n';
                break;
            }
        }
 
 
    }
    return 0;
}
 

 

 

알고리즘

1. 자물쇠는 사각형 모양이므로 n을 4로 나눈게 숫자가 된다. 따라서 가장 큰 수는 (2^4)^7  n 최대가 28

2. 뒤가 앞이랑 연결 되어야 한다. 하지만 전체를 보는게 아니라 n/4 - 1 만큼만 붙여서 보면 된다.

그래서 맨 뒤의 div - 1만큼 head에 붙여줬다.

반복문

3. 맨 앞부터 div 만큼 짤라서 long long으로 변환, vector에 push

4. 첫 번째 글자 제외하고 string 다시 재생성

string길이가 div보다 크거나 같을 때 계속 반복

 

5.vector내림차순으로 정렬

겹치지 않는 k번째 수 출력

 

속도도 나름 준수