[SWEA 5658] 보물상자 비밀번호 (Java)

SWEA 5658 보물상자 비밀번호

첫 인상에 비해서 쉬운 문제였지만 놓친 것이 몇 가지 있었던 아쉬운 문제였다. 문제를 잘 읽자, 정리를 잘 하자

문제 풀이

1. 자물쇠 각 변의 16진수를 10진수로 변환시켜 TreeSet에 삽입한다.
2. 시계 방향으로 회전한다.
3. N-1 번 회전하며 1~2를 반복한다.
4. TreeSet 을 배열로 바꾸고 length - K 번째 원소를 출력한다.

• TreeSet 을 사용한 이유는 TreeSet 의 삽입 연산은 정렬이 되기 때문인데 HashSet 을 사용하고 다시 정렬을 하는 것과 비교하여 어느 것이 더 나은지는 모르겠다...

다른 분의 코드를 보며 직접 회전을 구현할 필요가 없는 문제라는 것을 깨달았다.

• 어차피 N/4 만큼 끊어서 10진수로 변환하는 것이기 때문에 회전할 필요없이 16진수의 시작점을 1씩 늘려가는 것이 회전하는 것과 같다.
• String에 관하여...
  - String을 직접 이어 붙히는 것은 오버헤드가 크다. 따라서 StringBuilder를 사용하는 것이 좋다. 또한 sb.append() 와 sb.deleteCharAt(0) 을 사용한다면 라빈카프 문자열 알고리즘에서와 같은 원리로 효율을 극대화 할 수 있다.
• 자물쇠의 꼭지점에는 숫자가 없다.
  - 문제를 똑바로 읽자...

구현 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class S5658_모의보물상자비밀번호 {
	
	
	static int N, K, vertex;
	static String[] lock;
	static TreeSet<Integer> numbers;
	static StringTokenizer st;
	static StringBuilder sb;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		StringBuilder sb = null;
		
		int T = stoi(br.readLine());
		
		for(int t = 1 ; t <= T ; ++t) {
			st = new StringTokenizer(br.readLine());
			N = stoi(st.nextToken());
			K = stoi(st.nextToken());
			
			vertex = N / 4;
			lock = new String[N + 1];
			numbers = new TreeSet<>();
			
			char[] chars = br.readLine().toCharArray();

			for(int i = 1 ; i <= N ; ++i) {
				sb = new StringBuilder();
				sb.append(chars[i - 1]);
				lock[i] = sb.toString();
			}
			
			for(int i = 0 ; i < N - 1 ; ++i) {
//				System.out.println("==== " + i + "회전 =====");
				getNumbers();
				rotate();
			}
			
			Object[] arr = numbers.toArray();
			
			System.out.println("#" + t + " " + arr[arr.length - K]);
		}
		
	}
	
    // 배열을 시계방향으로 회전하는 함수
	private static void rotate() {
		String temp = lock[N];
		
		for(int i = N ; i > 1 ; --i) {
			lock[i] = lock[i - 1];
		}
		
		lock[1] = temp;
	}
	
    // 현재 상태에서 각 변의 수 구하기 함수
	private static void getNumbers() {
		sb = new StringBuilder();
		
		for(int i = 1 ; i <= N ; ++i) {
			sb.append(lock[i]); 
			if(i % vertex == 0) {
//				System.out.println(sb.toString());
				numbers.add(hexToDec(sb.toString()));
				sb = new StringBuilder();
			}
		}
	}
	
    // 16진수 -> 10진수 함수
	private static int hexToDec(String hex) {
		int dec = Integer.parseInt(hex, 16);
		
		return dec;
	}
	
	private static int stoi(String s) {
		return Integer.parseInt(s);
	}
}