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

문제

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

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

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

예를 들어 [Fig.1]의 수는 1A3, B54, 8F9, D66이고, [Fig.2]의 수는 61A, 3B5, 48F, 9D6이다.

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

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

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

[제약 사항]

1. N은 4의 배수이고, 8이상 28이하의 정수이다. (8 ≤ N ≤ 28)
2. N개의 숫자는 각각 0이상 F이하로 주어진다. (A~F는 알파벳 대문자로만 주어진다.)
3. K는 생성 가능한 수의 개수보다 크게 주어지지 않는다.

[예제]

아래와 같이 (1, B, 3, B, 3, B, 8, 1, F, 7, 5, E) 12개의 숫자가 주어지고 K가 10인 경우를 살펴보자.

이 경우에 생성 가능한 수는 각 회전 별로 다음과 같다.

0회전 : 1B3, B3B, 81F, 75E1회전 : E1B, 3B3, B81, F752회전 : 5E1, B3B, 3B8, 1F73회전 : 0회전과 동일

생성 가능한 수를 내림 차순으로 나열하면 다음과 같고, K(=10)번째로 큰 수는 503(=1F7)이다.(B3B를 중복으로 세지 않도록 주의한다.)

F75, E1B, B81, B3B, 81F, 75E, 5E1, 3B8, 3B3, 1F7, 1B3

[입력]

가장 첫 줄에는 테스트 케이스의 개수 T가 주어지고, 그 아래로 각 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 숫자의 개수 N과 크기 순서 K가 주어 진다.

그 다음 줄에는 16진수 0~F 숫자가 공백 없이 N개 주어진다.

[출력]

출력의 각 줄은 '#t'로 시작하고, 공백을 한 칸 둔 다음 정답을 출력한다.

(t는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)

풀이

소요시간 약 60분

1. 변의 갯수는 4개로 동일하다.
2. 회전 횟수는 전체 문자열의 길이 / 변의 갯수 - 1 이다. (만약 문자열의 길이가 16이라면, 변의갯수 4로 나눌 경우 수는 4글자가 나온다. 따라서 3회전까지 수행 후 4회전은 0회전과 동일하다.)
3. 각 문자열을 잘라서 list에 추가한다. 이 때, 숫자의 비교는 16진수로 변환하여 비교한다. 또한, 같은 문자열이 입력되었을 경우에는 0을 리턴하도록 처리해준다.
4. k번째 문자열을 16진수로 변환하여 출력한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Solution {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new java.io.InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int t = Integer.parseInt(br.readLine());
		
		for (int i = 1; i <= t; i++) {
			long answer = 0;
			
			String[] input = br.readLine().split(" ");
			int n = Integer.parseInt(input[0]);
			int k = Integer.parseInt(input[1]);
			
			int rotationCount = n / 4;
			

			String strings = br.readLine();
			ArrayList<String> queue = new ArrayList<String>();

			for (int j = 0; j < rotationCount; j++) {
				for (int l = 0; l < strings.length(); l = l + rotationCount) {
					String s = strings.substring(l, l + rotationCount);
					if (!queue.contains(s))
						queue.add(s);
				}
				String copy = strings.substring(0, strings.length()-1);
				strings = strings.charAt(strings.length()-1) + copy;
			}
			queue.sort(new Comparator<String>() {

				@Override
				public int compare(String o1, String o2) {
					if (o1.equals(o2)) return 0;
					long first = 0;
					long second = 0;
					for (int j = o1.length()-1; j >= 0; j--) {
						char c1 = o1.charAt(j);
						char c2 = o2.charAt(j);
						if (Character.isDigit(c1)) {
							first += ((int)c1 - '0') * Math.pow(16, o1.length() -1 - j);
						} else {
							first += ((int)c1 - 'A' + 11) * Math.pow(16, o1.length() -1-j);
						}
						if (Character.isDigit(c2)) {
							second += ((int)c2 - '0') * Math.pow(16, o1.length() -1-j);
						} else {
							second += ((int)c2 - 'A' + 11) * Math.pow(16, o1.length() -1 -j);
						}
					}
					return (int) (second-first);
				}
			});
			String ans = queue.get(k-1);
		
			for (int j = ans.length()-1; j >= 0; j--) {
				char c1 = ans.charAt(j);
				if (Character.isDigit(c1)) {
					answer += (c1 - '0') * Math.pow(16, ans.length() -1 - j);
				} else {
					answer += (c1 - 'A' + 10) * Math.pow(16, ans.length() -1-j);
				}
				
			}
			
			sb.append(String.format("#%d %d\\n", i, answer));
		}
		System.out.println(sb);
		
	}
}

 

문제 출처

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRUN9KfZ8DFAUo&categoryId=AWXRUN9KfZ8DFAUo&categoryType=CODE&problemTitle=%EC%97%AD%EB%9F%89&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1