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

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

---

1. 이해하기

• 보물 상자의 뚜껑은 시계방향으로 돌릴 수 있다.
• 보물 상자에는 자물쇠가 걸려있는데, 이 자물쇠의 비밀번호는 보물 상자에 적힌 숫자로 만들 수 있는 모든 수 중, K번쨰로 큰 수를 10진수로 만든 수이다.
• N개의 숫자가 입력으로 주어졌을 때, 보물상자의 비밀번호를 출력하는 문제.
• 크기 순서를 셀 때 같은 수를 중복으로 세지 않는다.
• 모든 경우에 나오는 수를 만들어보는 완전탐색문제.

---

2. 구현하기

• 보물 상자에 있는 자물쇠를 시계방향으로 돌리는 경우.

  void rotate() {
      int len = password.size();
      char c = password[len-1];
      for(int i = len-1; i >= 0; i--) {
          password[i] = password[i-1];
      }
      password[0] = c;
  }

• 자물쇠를 돌렸을 때, 나올수 있는 비밀 번호들을 set에 저장한다.

  • set에 저장하는 이유는 중복을 제거하기 위함이다.

  void add_pass() {
      int len = password.size();
      for(int i = 0; i <= len-len/4; i+=len/4) {
          string s = "";
          for(int j = 0; j < len/4; j++) {
              s += password[i+j];
          }
          pass.insert(s);
      }
  }

• 각 자물쇠의 길이만큼 회전을 시켜서 얻을 수 있는 비밀번호를 모두 구해본다.

  void solve() {
      int len = password.size();
      for(int i = 0; i < len/4; i++) {
          add_pass();
          rotate();
      }
  }

• 16진수를 10진수로 바꿔준다.

  int pow(int num, int idx) {
      int ret = 1;
      for(int i = 0; i < idx; i++) {
          ret *= num;
      }
      return ret;
  }
  
  int get_octal(string s) {
      int len = s.size();
      int ret = 0;
      int idx = 0;
      for(int i = len-1; i >= 0; i--) {
          if('0' <= s[i] and s[i] <= '9') {
              int num = s[i]-'0';
              ret += num*pow(16,idx++);
          } else {
              int num = 10+s[i]-'A';
              ret += num*pow(16,idx++);
          }
      }
      return ret;
  }

• set에 저장한 것들을 vector에 저장하고 정렬을 시켜서 K번째로 큰 수를 얻는다.

  bool comp(string a, string b) {
      return a > b;
  }
  
  int get_password() {
      vector<string> p;
      for(string s: pass) {
          p.push_back(s);
      }
      sort(p.begin(),p.end(),comp);
      string s = p[K-1];
      return get_octal(s);
  }

---

3. 전체 코드

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
set<string> pass;
string password;
int N,K;

void rotate() {
    int len = password.size();
    char c = password[len-1];
    for(int i = len-1; i >= 0; i--) {
        password[i] = password[i-1];
    }
    password[0] = c;
}

void add_pass() {
    int len = password.size();
    for(int i = 0; i <= len-len/4; i+=len/4) {
        string s = "";
        for(int j = 0; j < len/4; j++) {
            s += password[i+j];
        }
        pass.insert(s);
    }
}

void solve() {
    int len = password.size();
    for(int i = 0; i < len/4; i++) {
        add_pass();
        rotate();
    }
}

int pow(int num, int idx) {
    int ret = 1;
    for(int i = 0; i < idx; i++) {
        ret *= num;
    }
    return ret;
}

int get_octal(string s) {
    int len = s.size();
    int ret = 0;
    int idx = 0;
    for(int i = len-1; i >= 0; i--) {
        if('0' <= s[i] and s[i] <= '9') {
            int num = s[i]-'0';
            ret += num*pow(16,idx++);
        } else {
            int num = 10+s[i]-'A';
            ret += num*pow(16,idx++);
        }
    }
    return ret;
}

bool comp(string a, string b) {
    return a > b;
}

int get_password() {
    vector<string> p;
    for(string s: pass) {
        p.push_back(s);
    }
    sort(p.begin(),p.end(),comp);
    string s = p[K-1];
    return get_octal(s);
}

void input() {
    pass.clear();
    cin >> N >> K;
    cin >> password;
}

int main() {
    int T;
    cin >> T;
    for(int t = 1; t <= T; t++) {
        input();
        solve();
        cout << '#' << t << ' ' << get_password() << '\n';
    }
    return 0;
}