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

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRUN9KfZ8DFAUo&categoryId=AWXRUN9KfZ8DFAUo&categoryType=CODE&problemTitle=&orderBy=RECOMMEND_COUNT&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=2&&&&&&&&&

SW Expert Academy

최종 코드

• GitHub github.com/hwayeon351/SWEA-Algorithms

hwayeon351/SWEA-Algorithms

//
//  main.cpp
//  SWEA5658
//
//  Created by Hwayeon on 2021/02/02.
//

#include <iostream>
#include <vector>
#include <string>
#include <functional>
#include <algorithm>
using namespace std;

int N, K;
vector<char> _lock;
vector<int> passwords;

void get_passwords(){
    int cnt = _lock.size()/4;
    string new_pass = "0x";
    for(int i=0; i<_lock.size(); i++){
        int idx = i % cnt;
        new_pass += _lock[i];
        if (idx == cnt-1){
            bool check = true;
            for(int j=0; j<passwords.size(); j++){
                if(stoi(new_pass, nullptr, 16) == passwords[j]){
                    check = false;
                    break;
                }
            }
            if(check) passwords.push_back(stoi(new_pass, nullptr, 16));
            new_pass = "0x";
        }
    }
}

void rotate_lock(){   
    get_passwords();
    for(int i=0; i<N/4; i++){
        char temp;
        char before = _lock[0];
        _lock[0] = _lock[_lock.size()-1];
        for(int j=1; j<_lock.size(); j++){
            temp = _lock[j];
            _lock[j] = before;
            before = temp;
        }
        get_passwords();
    }
    sort(passwords.begin(), passwords.end(), greater<int>());
}

int main(int argc, char** argv) {
    int test_case;
    int T;
    cin>>T;
    for(test_case = 1; test_case <= T; ++test_case)
    {
        passwords.clear();
        _lock.clear();
        cin >> N >> K;
        for(int i=0; i<N; i++){
            char c;
            cin >> c;
            _lock.push_back(c);
        }
        rotate_lock();
        cout  << "#" << test_case << " " << passwords[K-1] << endl;
    }
    
    return 0;
}

 

---

풀이 과정

풀이 시간  1시간 35분

1. 변수 선언 및 입력 받아오기

 먼저, 입력인 N과 K를 선언한다. 그리고 보물 상자의 뚜껑인 벡터 _lock과 뚜껑을 돌리면서 생성되는 16진수를 10진수로 변환한 값들을 저장하는 벡터 passwords를 선언한다.

int N, K;
vector<char> _lock;
vector<int> passwords;

입력을 받아오기 전, 테스트케이스가 시작될 때, 앞에서 선언한 벡터 passwords와 _lock을 clear()해준다.

그리고 N과 K를 받아온 후, N개의 16진수의 숫자들을 각각 char형으로 받아와 _lock에 push 해준다.

    for(test_case = 1; test_case <= T; ++test_case)
    {
        passwords.clear();
        _lock.clear();
        cin >> N >> K;
        for(int i=0; i<N; i++){
            char c;
            cin >> c;
            _lock.push_back(c);
        }
        rotate_lock();
        cout  << "#" << test_case << " " << passwords[K-1] << endl;
    }

 

 

2. 생성 가능한 비밀번호 경우의 수 구하기 get_passwords()

 입력을 받아 온 후, rotate_lock()을 실행시키면 제일 먼저 get_passwords()가 실행된다. 따라서 get_passwords() 함수부터 설명하도록 하겠다.

void get_passwords(){
    int cnt = _lock.size()/4;
    string new_pass = "0x";
    for(int i=0; i<_lock.size(); i++){
        int idx = i % cnt;
        new_pass += _lock[i];
        if (idx == cnt-1){
            bool check = true;
            for(int j=0; j<passwords.size(); j++){
                if(stoi(new_pass, nullptr, 16) == passwords[j]){
                    check = false;
                    break;
                }
            }
            if(check) passwords.push_back(stoi(new_pass, nullptr, 16));
            new_pass = "0x";
        }
    }
}

0회전인 상태 혹은 회전이 일어난 후에 변화된 보물 상자의 뚜껑에서 생성된 16진수의 수를 10진수로 변환한다. 그 다음, 벡터 passwords에 같은 수가 있는지 중복체크를 하여 비밀 번호 후보를 passwords에 추가해주는 함수이다.

먼저, 변수 cnt는 뚜껑의 한 면에 적힌 16진수의 글자 수이다. 이는 곧 N/4(= lock.size())가 된다. for문을 통해 cnt씩 _lock에 저장된 글자들을 끊어서 변수 new_pass에 저장할 것이다.

new_pass = "0x"로 초기화 하여 16진수로 표현된 string 값으로 나타내주도록 하자.

 이제 N만큼 for문을 반복시켜 새로운 비밀번호 new_pass를 생성하고 중복체크를 해 passwords에 추가해주자.

1. idx는 new_pass의 몇 번째 글자에 해당하는지를 나타낸다. i % cnt를 하여 0부터 cnt-1까지의 인덱스를 통해 알 수 있다.
2. _lock[i]를 new_pass에 추가해준다.
3. idx == cnt-1이면, 즉, 사각형의 한 면에 적혀있는 16진수의 마지막 글자인 경우, stoi 함수를 통해 string으로 되어있는 16 진수 new_pass를 10진수로 변환하고 passwords에 이전에 추가된 적이 있는지 중복체크를 진행한다.
4. 중복이 없다면 passwords에 10진수로 변환한 값(int)을 push 해주고 그 다음 비밀번호 생성을 위해 new_pass를 다시 "0x"로 초기화 해준다.

 

3. 보물 상자의 뚜껑 회전하기 rotate_lock()

void rotate_lock(){   
    get_passwords();
    for(int i=0; i<N/4; i++){
        char temp;
        char before = _lock[0];
        _lock[0] = _lock[_lock.size()-1];
        for(int j=1; j<_lock.size(); j++){
            temp = _lock[j];
            _lock[j] = before;
            before = temp;
        }
        get_passwords();
    }
    sort(passwords.begin(), passwords.end(), greater<int>());
}

 이제, 보물 상자의 뚜껑을 회전해보자. 가장 먼저 0회전인 상태에서 발생되는 비밀번호 후보들을 벡터 passwords에 저장시켜주기 위해 위에서 설명한 get_passwords() 함수를 실행해준다.

그 다음, 보물 상자의 뚜껑을 회전시켜보자. 여기서 문제에서 직접적으로 언급하지 않았지만 중요한 점이 한 가지 있다. (나는 이점을 간과해서 거의 30분을 날려먹었다...) 바로 뚜껑의 한 면에 적힌 16진수의 글자 수만큼 회전시켜야 한다는 것이다.

나는 문제에 나온 예시에만 기울여서 3번만 회전시키면 되는 줄 알고 착각했다. 그 결과, 예제 1, 2번은 맞았으나 그 뒤론 실패했다. 문제에서 설명한 예시의 경우 N = 12이므로 뚜껑의 한 면에 16진수가 N/4 = 3글자씩 구성되어 있다. 그렇기 때문에, 3회전을 하기 까지는 다른 비밀번호 후보들이 발생하지만 4회전 이후에는 회전을 시키기 전과 동일하게 된다. 따라서 0회전부터 3회전까지만 살펴보면 된다.

 따라서, 서로 다른 모든 경우의 수를 발생시키기 위해 뚜껑의 한 면에 적히는 16진수의 글자 수인 N/4만큼 회전을 시켜야 한다.

이해가 되었다면 N/4만큼 for문을 반복시켜 회전을 시켜보자. 이때, 회전은 시계 방향으로 이뤄진다는 점에 기울여 이전 글자와 현재 글자를 temp와 before 변수를 통해 바꿔주도록 하자. 

1. 임시 저장소인 temp를 생성하고, before에 첫 글자인 _lock[0]을 담아준다. 회전을 하면 _lock[0]은 _lock의 마지막 글자가 되어야하므로 _lock[_lock.size()-1]로 바꿔준다.
2. for문을 통해 두 번째 글자부터 마지막 글자까지 모두 바꿔준다. temp에는 현재 글자 _lock[j]를 담아준 후, _lock[j]를 이전 글자 before로 바꿔준다. 그 다음 temp를 before에 담아준다.
3. 1회 회전을 마쳤으니까 get_passwords()를 실행해서 새 비밀번호들을 담아준다.

위 과정을 글자 수만큼 반복했다면, K번째로 큰 수를 알아내기 위해 passwords를 내림차순으로 sort해준다. sort함수는 algorithm 라이브러리에, greater<int>함수는 functional 라이브러리에 선언되어 있다.

 

 

---

참고

• 2021/02/03 - [C++] - [STL] algorithm

[STL] algorithm

• 2021/02/03 - [C++] - [STL] functional

[STL] functional