보물상자 비밀번호_5658

문제 출처 : 보물상자_5658

파라미터 정리

N 입력되는 숫자의 개수 (4의 배수, 8~28)
비밀번호를 구성하는 숫자 (0~9,A,B,C,D,E,F)
시계 방향으로 돌리면 숫자가 시계방향으로 한 칸씩 회전함
각 변에는 동일한 개수의 숫자 有 시계방향 순으로 높은 자리에 해당함
만들 수 있는 모든 수 중에서 k번째로 큰 수를 10진수로 변환한 것을 비밀번호로 가짐
N개의 숫자가 입력으로 주어질 때 비밀 번호를 출력하라
한 변에 있는 숫자 개수 = N/4;
0번 회전 = (N/4)번 회전

간략한 과정

input_1 테스트 케이스 T 입력받기
input_2 N,K 입력받기
input_2 숫자 N개 공백없이 입력받기
일단 숫자 N개부터 해체해서 배열에 넣기
0번~(N/4)번 회전하면서 발생하는 수 10진수 수로 변경해서 set에 넣기
sort를 이용해서 set 정렬
output k번째에 해당하는 숫자 반환하기

코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int T,N,K;
string list[28];
vector<int> myvec;

bool desc(int a, int b){ return a > b; }

int solve(){
    myvec.clear();
    int num = N/4;//3
    string pass = "";;
    for(int i = 0; i < num; i++){//012
        for(int j = 0; j < N; j++){//0~11
            int idx = (j+(N-1-i))%N;
            pass += list[idx];
            if((j+1)%num != 0) continue;
            int temp = stoi(pass,nullptr,16);
            myvec.push_back(temp);
            pass = "";
        }
    }
    sort(myvec.begin(), myvec.end(),desc);
    int cnt = 0,tmp = 0;
    for(int i = 0; i < myvec.size(); i++){
        if(myvec[i]==tmp) continue;
        cnt++;
        tmp = myvec[i];
        if(cnt == K) return tmp;
    }
    
    return -1;
}

int main()
{
    cin >> T;
    for(int t = 0; t < T; t++){
        string temp;
        cin >> N >> K >> temp;
        for(int i = 0; i < N; i++){
            list[i] = temp.substr(i,1);

        }
        cout << "#" << t+1 << " " << solve() << endl;
    }

    return 0;
}

다른 풀이

shift를 이용해서 하나씩 이동시키는 방법

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

int T;
int N,K;
int oneSize;
string num[28];

int solve(){
    string numList[7][28];
    
    for(int i = 0; i < oneSize; i++){
        for(int j = 0; j < N; j++){
            numList[i][j] = num[j];    
        }
        
        string temp = num[N-1];
        for(int x = N-1; x > 0; x--){
            num[x] = num[x-1];
        }
        num[0] = temp;
    }
    
    string pw = ""; int cnt = 0;
    vector<int> hexNumList;
    for(int i = 0; i < oneSize; i++){
        for(int j = 0; j < N; j++){
            pw += numList[i][j];
            cnt++;
            
            if(cnt == oneSize){
                hexNumList.push_back(stoi(pw, nullptr, 16));
                cnt = 0;
                pw = "";
            }
        }
    }
    
    sort(hexNumList.begin(), hexNumList.end(),greater<int>());
    
    int curr = 0; 
    cnt = 0;
    for(int i = 0; i < hexNumList.size(); i++){
        if(curr == hexNumList[i]) continue;
        cnt++;
        curr = hexNumList[i];
        if(cnt == K)
            return hexNumList[i];
    }
    
    return 0;
}

int main() {
    cin >> T;
    
    for(int t = 0; t < T; t++){
        string temp = "";
    
        cin >> N >> K >> temp;
            
        oneSize = N/4;
        
        for(int i = 0; i < N; i++){
            num[i] = temp.substr(i,1);
        }
        
        cout << "#" << t+1 << " " << solve() << endl;
    }
    
    return 0;
}

다른풀이

substr 이용해서 한글자씩 이동

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int T;
int N,K;
string hexText;

bool desc(int a, int b){
    return a > b;
}

int solve(){
    int rotSize = N/4;
    
    vector<int> valList;
    
    for(int i = 0; i < rotSize; i++){
        string last = hexText.substr(N-1);
        hexText = last + hexText.substr(0,N-1);
        
        for(int j = 0; j < 4; j++){
            string temp = hexText.substr(0+(j*rotSize),rotSize);
            valList.push_back(stoi(temp, nullptr, 16));
        }
    }
    
     sort(valList.begin(), valList.end(), desc);

    int cnt = 0, temp = 0;
    for(int k = 0; k < valList.size(); k++){
        if(valList[k] == temp) continue;
        cnt++;
        temp = valList[k];
        
        if(cnt == K) return temp;
    }
    
    return 0;
}

int main()
{
    cin >> T;
    
    for(int t = 0; t < T; t++){
        cin >> N >> K;

        cin >> hexText;

        cout << "#" << t+1 << " " << solve() << endl;
        
    }

    return 0;
}