SWEA의 프로세서 연결하기 문제를 풀어보고자 했습니다.

SWEA-보물상자 비밀번호

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

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

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

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

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

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

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

[제약 사항]

N은 4의 배수이고, 8이상 28이하의 정수이다. (8 ≤ N ≤ 28)

N개의 숫자는 각각 0이상 F이하로 주어진다. (A~F는 알파벳 대문자로만 주어진다.)

K는 생성 가능한 수의 개수보다 크게 주어지지 않는다.

[예제]

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

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

• 0회전 : 1B3, B3B, 81F, 75E
• 1회전 : E1B, 3B3, B81, F75
• 2회전 : 5E1, B3B, 3B8, 1F7
• 3회전 : 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부터 시작한다.)

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Scanner;

public class SWEA5658 {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int testCase = scanner.nextInt();
		for(int tc = 1; tc <= testCase; tc++) {
			int N = scanner.nextInt();
			int K = scanner.nextInt();
			char[] array = new char[N + N/4]; //앞에 되돌아 오는 경우까지 추가
			String str = scanner.next();
			
			HashSet<Integer> hash = new HashSet<Integer>();//중복제거하는 해쉬셋
			for(int i = 0 ; i < N ; i++)
				array[i] = str.charAt(i);
			for(int i = N; i < N+N/4; i++)
				array[i] = str.charAt(i-N); // 앞에 4개까지 받았다.
			for(int i = 0 ; i < array.length-N/4; i++) { // 처음부터 끝까지 한번 반복을해보자.
				String temp = "";
				for(int j = 0 ; j < N/4; j++) { // 4분의 1씩 짤라서 넣자.
					temp += array[i+j]; 
				}
				long hexa = Long.valueOf(temp, 16);//16진수로 변환
				hash.add((int) hexa);
			}
			
			ArrayList<Integer> list = new ArrayList<Integer>(hash);//리스트로 받고
			Collections.sort(list, Comparator.reverseOrder());//정렬하자
			System.out.println("#" + tc + " " + list.get(K-1)); // K번째로 큰애를 뽑자.
		}
		scanner.close();
	}
}

이번 문제는 HashSet을 사용해서 풀었습니다.

회전별로 끊은 숫자들 중 중복이 없는 경우만 얻어내기 위해서 HashSet을 사용했습니다.

	for(int i = 0 ; i < N ; i++)
		array[i] = str.charAt(i);
	for(int i = N; i < N+N/4; i++)
		array[i] = str.charAt(i-N); // 앞에 4개까지 받았다.

(1, B, 3, B, 3, B, 8, 1, F, 7, 5, E)를 예로 들었을 때

array에 들어가는 값들은 1, B, 3, B, 3, B, 8, 1, F, 7, 5, E + 1, B, 3 의 값이 들어가게 됩니다.

그에 대한 이유로는 한바퀴 다 돌았을 때 맨 앞라인 까지 추가로 넣어 주기 위해서 입니다.

	for(int i = 0 ; i < array.length-N/4; i++) { // 처음부터 끝까지 한번 반복을해보자.
		String temp = "";
		for(int j = 0 ; j < N/4; j++) { // 4분의 1씩 짤라서 넣자.
			temp += array[i+j]; 
		}
		long hexa = Long.valueOf(temp, 16);//16진수로 변환
		hash.add((int) hexa);
	}

array의 길이에서 N/4을 뺀 크기만큼 반복을 합니다.

이후 String temp를 이용해서 4분의 1사이즈만큼씩 잘라서 temp에 저장을 할 것입니다.

그러면 한번씩 돌면서 잘린 temp를 16진수로 변경 후 long형으로 바꾼것을 hexa 값에 넣습니다.

그리고 그 값을 int형으로 바꿔서 hash에 넣습니다.

그럼 HashSet은 중복된 값이있다면 걸러주고, 아니라면 넣게 됩니다.

	ArrayList<Integer> list = new ArrayList<Integer>(hash);//리스트로 받고
	Collections.sort(list, Comparator.reverseOrder());//정렬하자
	System.out.println("#" + tc + " " + list.get(K-1)); // K번째로 큰애를 뽑자.

이제 hash에 있는 값들을 arraylist로 넘겨줬습니다.

그에 대한 이유로는 Collections.sort를 이용해서 정렬하기 위해서입니다.

그럼 이제 K번째에 있는 값을 가져오도록 list의 get을 이용해 K번째의 값을 가져와 출력합니다.