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

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

SW Expert Academy

---

문제 해석

보물상자의 비밀번호를 찾는 문제로, N개의 숫자로 이루어진 원형 배열에서 4개의 변에 해당하는 N/4 길이의 숫자를 각 변마다 한 칸씩 회전하며 추출한다. 추출된 숫자들을 16진수로 해석하여 그 중 k번째로 큰 값을 찾아야 한다.

풀이 과정

1. 입력된 문자열을 주어진 길이에 따라 회전하면서 각 변에서 추출된 숫자를 수집한다.
2. 수집된 각 숫자를 16진수 값으로 변환하여 Map에 저장한다. Map을 사용하여 중복을 제거하고, 각 16진수 값을 저장한다.
3. Map에 저장된 값을 내림차순으로 정렬한다.
4. k번째로 큰 값을 반환한다.

코드

package edu.ssafy.im.SWEA.D0.No5658;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;

public class Solution {
	public static void main(String[] args) throws NumberFormatException, IOException {
		new Solution().io();
	}

	private int n;  // 전체 숫자 개수
	private int k;  // 찾아야 할 순위
	private Map<String, Integer> map;  // 중복을 제거한 16진수 값들을 저장하는 맵
	private int SIZE;  // 변의 길이
	private String s;  // 입력 받은 전체 숫자 문자열

	private void io() throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());  // 테스트 케이스 수
		for (int t = 1; t <= T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			n = Integer.parseInt(st.nextToken());
			k = Integer.parseInt(st.nextToken());
			SIZE = n / 4;  // 변의 길이 계산
			map = new HashMap<>();
			s = br.readLine();
			
			sb.append("#").append(t).append(" ").append(sol()).append("\n");
		}
		
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	private int sol() {
		getRotateSum();  // 초기 회전 없이 수집
		for (int i = 0; i < SIZE-1; i++) {
			rotate();  // 문자열을 1칸 회전
			getRotateSum();  // 회전 후 수집
		}
		
		int idx = 0, ans = 0;
		for (String key : sort()) {  // 저장된 값들을 내림차순으로 정렬
			idx++;
			ans = map.get(key);
			if (idx == k) {  // k번째로 큰 값을 찾음
				break;
			}
		}
		
		return ans;
	}
	
	private List<String> sort() {  // 내림차순 정렬
		List<String> keySet = new ArrayList<>(map.keySet());
		keySet.sort((o1, o2) -> map.get(o2) - map.get(o1));
		return keySet;
	}
	
	private void rotate() {  // 문자열을 1칸 회전
		char[] c = s.toCharArray();
		char tmp = c[c.length - 1];
		for (int i = c.length-1; i > 0; i--) {
			c[i] = c[i-1];
		}
		c[0] = tmp;
		s = String.valueOf(c);
	}
	
	private void getRotateSum() {  // 회전된 상태에서 숫자 추출 및 저장
		String n;
		for (int i = 0; i < s.length(); i += SIZE) {
			n = s.substring(i, i+SIZE);
			map.put(n, getHexSum(n));
		}
	}
	
	private int getHexSum(String n) {  // 16진수로 변환
		int sum = 0;
		int i = SIZE-1;
		for(int c : n.toCharArray()) {
			if ('0' <= c && c <= '9') c -= '0';
			else c -= 'A' - 10;
			int x = (int) Math.pow(16, i--);
			sum += x * c;
		}
		return sum;
	}
}

시간 복잡도 분석

문자열을 회전하고 각 회전마다 모든 변의 값을 계산하는데 O(n)의 시간이 필요하며, 각 값을 16진수로 변환하는 데 O(SIZE)가 필요하다. 모든 회전은 최대 SIZE-1번 발생하므로, 전체 시간 복잡도는 O(n * SIZE)이다.

느낀점

이 문제는 원형 배열의 회전과 회전에 따른 숫자 추출, 그리고 그 숫자들을 16진수로 변환하여 k번째로 큰 값을 찾는 복합적인 작업을 요구한다. 중복 제거를 위해 Map을 사용하는 것이 중요했으며, 각 단계에서의 데이터 처리를 효율적으로 관리하는 것이 핵심적인 도전이었다.