SEA5658_보물상자 비밀번호

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRUN9KfZ8DFAUo

문제정리

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

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

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

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

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

6. 8<=N<=28(4의 배수) 숫자의 개수

K 크기 순서

16진수 0~F 숫자가 공백없이 N개 주어진다

문제issue

1. N에 따라서 최대 회전 회수가 정해진다

N = 8 이면 회전 = 1

N = 12 면 회전 = 2

N = 16 이면 회전 = 3

N = 20 이면 회전 = 4

N = 24 이면 회전 = 5

N = 28 이면 회전 = 6

해결흐름

1. N 크기의 배열에 N개의 숫자 넣는다

2. N/4자리씩 끊어서 10진수로 변환한 숫자를 저장한다

3. 회전한다

4. 10진수로 변환한 숫자를 저장한 배열이든 리스트든 sort 및 중복제거 한다

5. K번째 숫자를 도출한다

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.StringTokenizer;
 
import javax.xml.bind.annotation.adapters.HexBinaryAdapter;
 
public class Solution {
 
    public static void main(String[] args) throws Exception {
        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int test_case = Integer.parseInt(br.readLine().trim());
        for (int t = 1; t <= test_case; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
            int N = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());
            char[] arr = new char[N];
            int[] number = new int[N];
            String s = br.readLine();
            for (int i = 0; i < N; i++) {
                arr[i] = s.charAt(i);
            }
            // start
            // arr에서 N/4 만큼 끊어서 십진수로 변환하고 number에 저장
            int loop = 0;
            int number_idx = 0;
            while(true) {
                if(loop == N/2-1) {
                    break;
                }
                // 숫자 저장
                for (int i = 0; i < arr.length; i+=N/4) {
                    // temp에 끊은 자리수를 넣고
                    int[] temp = new int[N/4];
                    int temp_idx = 0;
                    for (int j = i; j < i+N/4; j++) {
                        if(arr[j] == 'A') {
                            temp[temp_idx++] = 10;
                        } else if(arr[j] == 'B') {
                            temp[temp_idx++] = 11;
                        } else if(arr[j] == 'C') {
                            temp[temp_idx++] = 12;
                        } else if(arr[j] == 'D') {
                            temp[temp_idx++] = 13;
                        } else if(arr[j] == 'E') {
                            temp[temp_idx++] = 14;
                        } else if(arr[j] == 'F') {
                            temp[temp_idx++] = 15;
                        } else {
                            temp[temp_idx++] = arr[j] - '0';
                        }
                    }
                    // temp에 있는 16진수를 10진수로 변경해서 number_10에 더하고 number 배열에 저장
                    int hex_number = 1;
                    int number_10 = 0;
                    for (int j = temp.length-1; j >= 0; j--) {
                        number_10 += temp[j] * hex_number;
                        hex_number *= 16;
                    }
                    if(number_idx < N) {
                        number[number_idx++] = number_10;
                    }
                }
                // arr을 회전
                char temp = arr[arr.length-1];
                for (int i = arr.length-2; i >= 0; i--) {
                    arr[i+1] = arr[i];
                }
                arr[0] = temp;
                loop++;
            }
            // 중복 제거 및 내림차순 정렬 후 K번째 숫자 출력
            HashSet<Integer> hash = new HashSet<>();
            List<Integer> list = new ArrayList<Integer>();
            for (int i = 0; i < number.length; i++) {
                hash.add(number[i]);
            }
            for (Integer i : hash) {
                list.add(i);
            }
            Collections.sort(list, new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o2-o1;
                }
            });
            for (int i = 0; i < list.size(); i++) {
                number[i] = list.get(i);
            }
            System.out.println("#" + t + " " + number[K-1]);
        } // end of test_case
    } // end of main
} // end of class