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

생각

길이가 N인 암호가 주어지며 이 암호는 4의 배수이다.
면이 4인 보물 상자 뚜껑이 주어지고 N인 길이의 암호가 이 뚜껑을 감싸고 있을 때, 시계 방향으로 뚜껑을 회전
시키면 적혀있는 암호가 1자리씩 시계 방향으로 이동한다. 이때, 한 면씩 적혀있는 16진수를 10진수로 
바꾸었을 때, 회전하여 구할 수 있는 모든 수중 K 번째 큰 수가 암호이다. 
이 암호를 구하여라.

처음 생각

처음에 뚜껑의 4면으로 나누는게 이해가 안갔었다. 주어진 암호가 4의 배수이므로 4로 나누어서 몫만큼씩 한 면으로 생각하면 됐다.

다음 생각

시계방향 회전을 해주어야하므로 배열을 이용해서 암호들을 넣었다. rotate() 메소드를 구현하여 회전을 하였다.

다다음 생각

회전을 구현 한 뒤, 암호를 구하기 위해 먼저 각 면의 암호들을 차례대로 쓴 후, 16진수를 10진수로 바꾸어야하므로 배열을 4로 나눈 몫씩 묶음으로 문자열로 만든 뒤 Integer.parseInt(문자열,16)을 이용해서 16진수를 10진수 Int 형으로 변환하였다.

▶이때, 중복된 암호는 제외 및 결과를 얻을 때, 암호중 10번 째로 큰 수를 위한 정렬을 위해서 List를 사용하여 list에 포함 되어있는지 확인 후, 암호를 반영해 주었다.

다다다음 생각

회전하여 구할 수 있는 모든 수중 K 번째 큰 수를 감안하지 않고 List에 저장된 수가 K를 넘으면 반복문을 빠져나오도록 하였더니 예제에서 틀린 케이스들이 나왔다.

▶문제를 항상 주의 깊게 보는 습관을 더 들여야 할 것 같다. 만약 실제 시험에서 테스트 케이스가 이런 실수를 예상해서 K 번째를 딱 딱 맞춰주었다면 제출 결과를 알 수 없기 때문에 테스트 케이스는 맞다고 생각하나 실제로는 틀린 알고리즘이 될 것이다. 항상 문제를 또박또박 읽기!!

다다다다음 생각

회전 후, List에 추가가 한 번도 안되면 반복문을 빠져나오도록하여 회전하여 구할 수 있는 모든 암호를 구한뒤 정렬하여 K 번째큰 암호를 구하였다.

방안

1) 처음에 배열을 int 형으로 만들었다가 16진수는 문자도 들어가므로 char 형으로 바꾸었다.

2) List의 내림차순 배열을 위해서 오름차순 정렬을 한 뒤, 뒤집었다.

▶그냥 오름차순 정렬 후, 뒤에서 K 번째를 확인해도 되고 Collections.sort() 시에 비교연산으로 Collections.reverse()를 주어 깔끔하게 한 줄로 해도 괜찮을 것 같다.

3) List는 index가 0부터 시작하므로 K-1 번째가 답이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;
 
public class Solution{
    static int n,k,cut;
    static char[] arr;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int tc = Integer.parseInt(br.readLine());
        for(int i=1;i<=tc;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            k = Integer.parseInt(st.nextToken());
            String t = br.readLine();
            arr = new char[t.length()];
            for(int j=0;j<t.length();j++)
                arr[j] = t.charAt(j);
            cut = t.length()/4;
            list.clear();
            solve();
            Collections.sort(list);
            Collections.reverse(list);
            sb.append("#"+i+" "+list.get(k-1)+"\n");
        }
        System.out.print(sb);
    }
    
    static     List<Integer> list = new ArrayList<>();
    private static void solve() {
        boolean flag = true;
        // 원하는 개수만큼 도달할 때까지
        while(flag) {
            flag = false;
            // 우선적으로 숫자를 뽑아내기
            for(int i=0;i<arr.length;) {
                int idx=0;
                String sNum = "";
                while(idx!=cut) {
                    sNum += arr[i++];
                    idx++;
                }
                int t = getInt(sNum);
                if(!list.contains(t)) {
                    list.add(t);
                    flag = true;
                }
            }
            // 회전 시키기
            rotate();
        }
    }
    
    private static int getInt(String t) {
        return Integer.parseInt(t,16);
    }
    
    private static void rotate() {
        // 시계 방향 회전이니 가장 마지막걸 저장
        char lastN = arr[arr.length-1];
        for(int i=arr.length-1;i>0;i--)
            arr[i] = arr[i-1]; 
        arr[0] = lastN;
    }
}