[SWEA] 5658. 보물상자 비밀번호

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

SW Expert Academy

문제

각 변에 다음과 같이 16진수 숫자(0~F)가 적혀 있는 보물상자가 있다.

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

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

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

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

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

 풀이

1. 상자의 변은 4개 이므로 N/4 만큼 회전을 하면 처음과 같은 상태가 되므로 N/4번 동안 각 변을 16진수 정수로 만들어주고(findPWD) 회전해주는(Rotate) 과정을 반복한다.
   1. 문자열을 N/4 크기만큼 잘라서 16진수 정수로 변환하여 box배열에 저장한다.
   2. box 배열에 들어있는 값이 현재 list에 존재하지 않는다면 list에 추가(중복 제거)
   3. 문자열의 마지막 문자를 맨 앞에 붙여줘서 회전을 해준다.
2. 모든 가능한 16진수를 만들어줬으면 정렬해준 후 K번째 큰 수를 구한다.
   1. K번째 큰 수를 10진수로 변환하기 위해 먼저 String으로 변환한다.
   2. String을 다시 10진수로 변환해서 출력.

 

import java.io.*;
import java.util.*;

public class Solution {
	static int N;
	static String s;
	static ArrayList&ltInteger> list;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for(int tc=1; tc<=T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			int K = Integer.parseInt(st.nextToken());
			s = br.readLine();
			list = new ArrayList&ltInteger>();

			for(int i=0; i<N/4; i++) {
				findPWD();
				rotate();
			}
			
			Collections.sort(list);
			String tmp = Integer.toString(list.get(list.size()-K));
			int ans = Integer.parseInt(tmp, 10);
			System.out.println("#"+tc+" "+ans);
		}
	}
	
	static void findPWD() {
		int[] box = new int[4];
		int k = N/4;
		
		int index = 0;
		for(int i=0; i<N; i+=k) {
			String tmp = s.substring(i, i+k);
			box[index++] = Integer.parseInt(tmp,16);
		}
		
		for(int i=0; i<4; i++) {
			if(!list.contains(box[i])) {
				list.add(box[i]);
			}
		}
	}
	
	static void rotate() {
		String last = s.substring(N-1);
		s = last+s.substring(0, N-1);
	}
}