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

문제

• SWEA 5658
• 문제의 저작권은 SW Expert Academy에 있습니다.

접근방식

보물상자위의 수들은 시계방향으로 회전하다가 처음 순서를 유지하기 전까지 N/4만큼의 수를 생성하고, 이렇게 생성된 수들 중 K번째로 작은 수를 10진수로 바꿔서 구하면 되는 문제이다.
꼬여있는 부분 없이 문제에서 주어진대로 구현하면 되서 크게 어렵지 않았다.
N개의 수가 모든 회전 후 다시 처음 자리로 돌아오기 까지는 N번 회전을 해야한다.
따라서 while문으로 N번 회전해주고 이렇게 생긴 리스트는 각 변만큼, 즉 N/4만큼 끊어서 새로운 수를 생성한다.
이렇게 생성한 수는 TreeSet에 담아서 중복되는 수는 자동으로 빼주었다.

1. 시계방향으로 N-1번 회전한다.
2. 1로 만들어진 수들을 N/4개씩 나눠서 TreeSet에 넣어준다.
3. TreeSet은 기본적으로 오름차순이기 때문에, 내림차순을 위한 리스트를 생성한 후 여기서 K번째에 해당하는 숫자를 구한다.
4. 3에서 구한 숫자는 16진수이므로 10진수로 바꾼 후 StringBuilder에 누적한다.

이 문제의 핵심은 TreeSet을 떠올릴 수 있는가, 16진수를 10진수로 바꿀 수 있는가 인 것 같다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Solution {

	static int T, N, K; // 테케, 숫자개수, 답이 되는 순서
	static char[] boxes; // 보물상자에 나열된 수
	static char[] origin; //원래 나열된 수
	static TreeSet<String> trees; // 생성된 수 리스트

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		T = Integer.parseInt(br.readLine());
		StringTokenizer st;
		StringBuilder ans = new StringBuilder();

		for (int tc = 1; tc <= T; tc++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());
			
			String input = br.readLine();
			boxes = new char[N];
			origin = new char[N];
			trees = new TreeSet<>();
			
			for(int i=0; i<input.length(); i++) {
				boxes[i] = input.charAt(i);
				origin[i] = input.charAt(i);
			}//End input
			
			//시계방향 회전 -> 오른쪽으로 한칸씩 밈, N번 회전하면 원래대로 돌아온다.
			int cnt = 0;
			while(cnt++ < N) {
				char tmp = boxes[N-1];
				for(int i=N-1; i>=1; i--) boxes[i] = boxes[i-1];
				boxes[0] = tmp;
				
				//N/4만큼 끊어서 수 생성 후 treeSet에 넣어줌(중복x)
				StringBuilder sb = new 	StringBuilder();
				for(int i=0; i<N; i++) {
					if(i % (N/4+1) == 0) {
						trees.add(sb.toString());
						sb = new StringBuilder();
						continue;
					}
					sb.append(boxes[i]);
				}
			}//End rotate
			
			
			Iterator<String> itr = trees.iterator();
			List<String> descending = new ArrayList<>(); //내림차순 리스트
			
			while(itr.hasNext()) {
				String s = itr.next();
				descending.add(s);
			}
			
			Collections.sort(descending, Collections.reverseOrder());
			String result = descending.get(K-1); //K번째로 작은 수
			
			//10진수로 바꿔주기
			ans.append("#"+tc+" "+Integer.parseInt(result, 16)+"\n");
		} // End testCase
		System.out.println(ans+"");
	}
}