문제
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRUN9KfZ8DFAUo
풀이
조건대로 구현하기만 하면 되는 문제이다. 더 쉽고 빠르고 효율적인 방법이 있겠지만 시간 관계 상 그냥 가장 먼저 생각나는 방법으로 구현했다. 문제에서 사각형의 각 변에 암호가 같은 수 만큼 나뉘어서 들어가는데 그걸 한 칸 씩 돌려서 변에 나타나는 숫자 중 k번째로 큰 수를 찾는 것이다.
1. deque과 string
위의 그림에서 한 번 회전하면 왼쪽 상단 변의 1B3 중 3이 오른쪽 상단으로 이동하고, 오른쪽 상단의 끝 숫자는 오른쪽 하단으로, ... 이런 식으로 돌아가는 것이다. 즉, 각 변에서 앞과 뒤에 추가 및 삭제가 일어나야 하는데, 보자마자 deque이 떠올라서 이 방법으로 구현했다. 혹은 암호 한 줄을 string으로 받아오므로 4개의 부분 string으로 나눠서 앞 뒤로 추가 및 삭제를 해도 됐는데, 역할은 같으니 별 상관은 없을 것 같다.2. 16진수를 10진수로 변환
각 변에 나타나는 수는 16진수이다. 16진수를 10진수로 변환하는 방법은 아래의 예와 같이 한다.123ABC...F = 1 * 16 ^ (n -1) + 2 * 16 ^ (n - 2) ^ ... + F(15) * 1
이 때, 16진수의 자릿수에 들어갈 수 있는 숫자는 아래의 규칙을 따른다.
| 10진수 | 16진수 |
| 0 | 0 |
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 4 |
| 5 | 5 |
| 6 | 6 |
| 7 | 7 |
| 8 | 8 |
| 9 | 9 |
| 10 | A |
| 11 | B |
| 12 | C |
| 13 | D |
| 14 | E |
| 15 | F |
예를 들어 1F = 1 * 16 + F * 1 = 1 * 16 + 15 * 1 = 16 + 15 = 31이며, 1D3 = 1 * 16 ^ 2 + D * 16 + 3 * 1 = 1 * 16 ^ 2 + 13 * 16 + 3 * 1 = 256 + 208 + 3 = 467 이다.
C++에서 거듭제곱 연산을 처리하는 함수가 있는데, #include <math.h> 의 pow(double x, double y)이다. 이걸 잊어버려서 그냥 for문으로 거듭제곱 연산을 만들어 줬는데.. 알면 편해진다. 외워두자.
3. Set
모서리에 나타나는 수를 전부 ans에 담았는데, 주의할 점은 숫자의 크기를 비교하는 것이므로 중복이 되는 것은 제거해줘야한다. 중복 제거하면 set 자료구조가 가장 먼저 떠오르게 된다. set을 내림차순 정렬시켜 전부 집어넣고 앞에서부터 10번째 숫자를 출력하도록 하자. 내림차순 정렬을 원한다면set<int, greater<int> s;
와 같은 형태로 정의하면 된다. default는 오름차순 정렬이다.
#include<iostream> #include <queue> #include <set> using namespace std; // 16진수를 변환한 10진수를 담는 set set<int, greater<int>> ans; void calc(deque<char> dq){ // 16을 몇번 곱해야하는지 체크하기 위한 변수 int mul = (int)dq.size(); int add = 0; // 덱의 16진수를 10진수로 변환 for(int i = 0; i < dq.size(); i++){ // 맨 앞부터 16 * (n - 1), 16 * (n - 2) ... int multiple = 1; for(int i = 1; i < mul; i++){ multiple *= 16; } // 0 ~ 9이면 그냥 int형으로만 변환해준다. if(dq[i] >= '0' && dq[i] <= '9'){ add = add + (dq[i] - 48) * multiple; } // A ~ F이면 10 ~ 15이므로 아래처럼 각 숫자를 변환해준다. else if(dq[i] >= 'A' && dq[i] <= 'F'){ add = add + (dq[i] - 'A' + 10) * multiple; } mul--; } ans.insert(add); } int main(int argc, char** argv) { int test_case; int T; cin>>T; for(test_case = 1; test_case <= T; ++test_case) { deque<char> one, two, three, four; int n, k; string s; cin >> n >> k; cin >> s; // string을 4등분해서 각각의 모서리 덱에 넣어준다. for(int i = 0; i < n / 4; i++){ one.push_back(s[i]); } for(int i = n / 4; i < n / 4 * 2; i++){ two.push_back(s[i]); } for(int i = n / 4 * 2; i < n / 4 * 3; i++){ three.push_back(s[i]); } for(int i = n / 4 * 3; i < n / 4 * 4; i++){ four.push_back(s[i]); } // 한번 회전할 때 마다 각 덱이 앞의 문자를 다음 모서리로 준다. for(int i = 1; i <= n; i++){ int back_1 = one.back(), back_2 = two.back(), back_3 = three.back(), back_4 = four.back(); one.pop_back(); two.push_front(back_1); two.pop_back(); three.push_front(back_2); three.pop_back(); four.push_front(back_3); four.pop_back(); one.push_front(back_4); // 10진수 변환 연산 실행 calc(one); calc(two); calc(three); calc(four); } // 내림차순 정렬된 set에서 10번째를 출력해준다. int idx = 0; set<int> :: iterator iter; for(iter = ans.begin(); iter != ans.end(); iter++){ if(idx == k - 1){ cout << "#" << test_case << " " << *iter << '\n'; break; } idx++; } ans.clear(); one.clear(); two.clear(); three.clear(); four.clear(); } return 0;//정상종료시 반드시 0을 리턴해야합니다. }
댓글
댓글 쓰기