문제

SWEA_5658_보물상자 비밀번호

요약

정사각형 형태의 보물상자 뚜껑 네 변에 총 $N$개의 16진수 숫자(0~F)가 적혀 있다.
상자를 시계 방향으로 한 칸씩 회전시킬 수 있으며, 회전할 때마다 네 변에 위치한 숫자들(각 변마다 $N/4$자리 수)을 읽어 16진수 숫자를 만든다.
생성 가능한 모든 16진수 중 중복을 제거하고 내림차순으로 정렬했을 때, $K$번째로 큰 수를 10진수로 변환하여 출력한다.

접근

문제를 봤을 때, 별다른 알고리즘이 떠오르기보단 자료구조를 무엇을 선택할까가 가장 중요하고 고민되었던 지점이다.
번호 중복이 되면 안되니 이를 Set으로 관리하고, 이 Set에 저장된 것들을 배열로 바꿔서 정렬하면 되겠다는 생각이 들었다.

회전시켜야하니까, 이를 Queue를 활용해서 앞에걸 빼서 뒤에 집어넣으면 되겠다 생각했다.
근데 이는 알고보니 '반시계' 방향이었다. 시계 방향으로 회전시키기 위해선 뒤에서 빼서 앞으로 집어넣어야한다. 그래서 Deque을 써야한다!

그리고 16진수를 10진수로 바꾸는 함수를 만들고, N/4의 개수가 되면 이를 변환할 수 있는 함수 총 2개를 만들어야겠다 생각했다.

알고리즘

1. 시계 방향 회전을 위한 Deque 활용

• 상자가 시계 방향으로 회전하는 형태이므로, 맨 뒤의 원소를 꺼내 맨 앞에 삽입하는 연산이 필요해 양방향 입출력이 가능한 Deque 자료구조로 회전을 구현한다.

2. $N/4$ 단위 분할 및 진법 변환

• 상자가 1칸 회전할 때마다 네 변의 숫자들을 $N/4$개씩 잘라 16진수 문자열을 만들고, 이를 10진수 정수로 변환한다.

3. Set을 통한 중복 제거

• 동일한 숫자가 여러 번 생성될 수 있으므로, 변환된 10진수 값들을 Set 자료구조에 추가하여 중복을 자동으로 걸러낸다. 한 변의 길이가 $N/4$이므로 총 $N/4$번만 회전시키면 모든 가능한 조합을 수집할 수 있다.

4. 배열(List) 변환 후 정렬 및 $K$번째 값 추출

• Set에 모인 고유한 숫자들을 배열(List)로 변환한 뒤 내림차순으로 정렬하고, $K$번째($K-1$ 인덱스) 원소를 정답으로 도출한다.

제출 코드

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

public class Main
{
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st; // = new StringTokenizer()
		
		int T = Integer.parseInt(br.readLine());
		for (int tc=1; tc<=T; tc++) {
		    st = new StringTokenizer(br.readLine());
		    int N = Integer.parseInt(st.nextToken());
		    int K = Integer.parseInt(st.nextToken());
		    // 비밀번호 숫자들 받음
		    String passwords = br.readLine();
		    // 각 번호들 저장
		    ArrayDeque<String> numbers = new ArrayDeque<>();
		    
		    for (int i = 0; i < N; i++) {
		        numbers.offer(passwords.charAt(i)+"");
		    }
		    
		    Set<Integer> set = new HashSet<>();
		    
		    // N/3번 돌린다 (다시 원래 위치로 번호들이 오게되는 총 회전 수)
		    for (int i=0; i<N/4; i++) {
		        // N번 돌리면서 q에서 빼고 집어넣으며 숫자조합 만듦
		        String num = "";
		        for (int j=0; j<N; j++) {
		            // 앞의 숫자를 빼고 뒤에 넣는다. 그러면서 모든 3자리 숫자 체크
		            String temp = numbers.pollFirst();
		            num += temp;
		            numbers.offerLast(temp);
		            // 3번 돌렸으면 이를 10진수로 바꿔서 Set에 박음
		            if (num.length() == N/4) {
		                // 숫자로 변경
		                int pwd = strToInt(num);
		                set.add(pwd);
		                num = "";
		            }
		        }
		        // 앞을 빼서 뒤로 넣는다.
		        String front = numbers.pollLast();
		        numbers.offerFirst(front);
		    }
		    
		    // Set의 값들을 배열로 변경
    	    int[] pwdList = new int[set.size()];
    	    int idx = 0;
    	    for (int pwd : set) {
    	        pwdList[idx++] = pwd;
    	    }
    	    
    	    Arrays.sort(pwdList);
    	    int kPwd = pwdList[set.size()-K];
    	    sb.append("#").append(tc).append(" ").append(kPwd).append("\n");
		}
		System.out.print(sb.toString());
	}
	
	// 16진수 -> 10진수
	public static int c16to10(String num16) {
	    char c = num16.charAt(0);
	    int num10 = 0;
	    if (c > '9') {
	        num10 = c-'A'+10;
	    }
	    else {
	        num10 = c-'0';
	    }
	    return num10;
	}
	
	// 숫자로 변환!
	public static int strToInt(String num) {
	    int res = 0;
	    String[] nums = num.split("");
	    for (int i=0; i<nums.length; i++) {
	        // 각 자리 숫자
	        int n = c16to10(nums[i]);
	        res += Math.pow(16, nums.length-1-i)*n;
	    }
	    return res;
	}
}

어려웠던 점

1. StringTokenizer!! 이거는 한글자한글자 못 뜯어낸다! 띄어쓰기가 있을 때만 쓰고, 구분자가 없는 경우엔 charAt()이나 split()으로 뜯어내야한다!
2. 시계 방향, 반시계 방향이 너무 헷갈렸다..
   처음엔 그냥 Queue를 썼는데, 왜 안되지 하고 계속 코드 고치다가 도저히 안풀려서 Gemini에게 힌트를 달라고하니, Deque로 해야 시계방향으로 회전된다는걸 알았다...
   Deque의 메서드도 좀 잘 알아야겠다!
3. 그리고 내림차순을 해야했는데, 이를 고려못하고 그냥 오름차순에서 K값을 찾으려했다... Collections.reverse()에 익숙해지자!

새로 알게 된 점

1. 완벽히 회전시켜야한다면 똑같은걸 뒤에 한번 더 붙이면 된다!

• 알고있었는데, 이 문제를 봤을 때, 생각이 안났다... 익숙해지도록 연습하자!

2. String의 16진수를 바로 10진수로 바꿀 수 있다니!
   Integer.parseInt("1F4", 16);
   이거면 바꿀 수 있다는걸 처음 알았다... 직접 16진수 변환하는 코드 짰는데...

최적화한 코드

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

public class Main
{
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st; // = new StringTokenizer()
		
		int T = Integer.parseInt(br.readLine());
		for (int tc=1; tc<=T; tc++) {
		    st = new StringTokenizer(br.readLine());
		    int N = Integer.parseInt(st.nextToken());
		    int K = Integer.parseInt(st.nextToken());
		    // 비밀번호 숫자들 받음
		    String passwords = br.readLine();
		    // 비밀번호 rotate하는 대신 2번 반복시켜서 rotate하는 효과 만듦
		    String rotatedPwd = passwords+passwords;
		    // 중복 비밀번호 처리를 위한 Set
		    Set<Integer> set = new HashSet<>();
		    
		    // 한 변에 N/4만큼 숫자들이 있을 수 있으니 N/4번 반복
		    for (int i=0; i<N/4; i++) {
		        // N/4의 길이만큼 띄어서 비밀번호로 자르도록 함
		        for (int j=i; j<N; j+=N/4) {
		            // N/4의 길이만큼 자름
		            String pwd = rotatedPwd.substring(j, j+N/4);
		            // String의 16진수를 10진수로 변환
		            int intPwd = Integer.parseInt(pwd, 16);
		            // Set에 집어넣어서 중복제거 처리
		            set.add(intPwd);
		        }
		    }
		    
		    // Set의 값들을 배열로 변경
    	    int[] pwdList = new int[set.size()];
    	    int idx = 0;
    	    for (int pwd : set) {
    	        pwdList[idx++] = pwd;
    	    }
    	    
    	    Arrays.sort(pwdList); // 오름차순 정렬
    	    // N번째로 큰걸 알기 위해 역순으로 접근 (내림차순)
    	    int kPwd = pwdList[set.size()-K];
    	    // Arrays.sort(pwdList, Collections.reverseOrder()); (내림차순)
    	    // int kPwd = pwdList[K];
    	    sb.append("#").append(tc).append(" ").append(kPwd).append("\n");
		}
		System.out.print(sb.toString());
	}
}