✔문제링크

SWEA5658. 보물상자 비밀번호

📝문제설명

💡해결방법

1. 현재 사각형에서 4개의 번호를 뽑는다.
2. map을 통해 중복여부를 확인하고 우선순위 큐에 삽입
3. 사각형을 회전시킨다.
4. 우선순위 큐에서 k번째 큰 수를 뽑는다.

👍코드

package 모의역량테스트;

import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Scanner;

public class SWEA5658보물상자비밀번호 {

	static int T, N, K, ans;
	static int[] numbers;
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		T = sc.nextInt();
		for(int tc=1; tc<=T; tc++) {
			N = sc.nextInt();
			K = sc.nextInt();
			sc.nextLine();
			
			Map<Integer, Integer> map = new HashMap<>();
			PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
			StringBuilder sb =new StringBuilder(sc.nextLine());
			// 1. 사각형의 회전 수
			for(int k=0; k<N/4; k++) {
				// 2. 현재 사각형에서 4개의 번호를 뽑는다.
				for(int i=1; i<=sb.length(); i++) {
					if(i%(N/4) == 0) {
						int num = converToInt(sb.substring(i-N/4, i));
						// 3. 중복여부를 확인하고 pq에 삽입
						if(!map.containsKey(num)) {
							map.put(num, num);
							pq.add(num);
						}
					}
				}
				
				// 4. 사각형 회전
				int last = sb.length();
				char ch = sb.charAt(last-1);
				sb.deleteCharAt(last-1);
				sb.insert(0, ch);
			}
			
			int cnt = 0;
			while(!pq.isEmpty()) {
				if(++cnt == K) {
					ans = pq.poll();
					break;
				}
				pq.poll();
			}
			
			System.out.println("#"+tc+" " + ans);
		}
	}
	private static int converToInt(String str) {
		int size = str.length();
		int num = 0;
		
		for(int i=0; i<size; i++) {
			int n = change(str.charAt(i));
			num+= n*Math.pow(16, (size-1-i));
		}
		
		return num;
	}
	private static int change(char ch) {
		int ans = 0;
		
		switch (ch) {
		case 'A':
			ans = 10;
			break;
		case 'B':
			ans = 11;
			break;
		case 'C':
			ans = 12;
			break;
		case 'D':
			ans = 13;
			break;
		case 'E':
			ans = 14;
			break;
		case 'F':
			ans = 15;
			break;

		default:
			ans = ch-'0';
			break;
		}
		
		return ans;
	}
}

😭새롭게 배운점

---

1. TreeSet
TreeSet 클래스는 데이터가 정렬된 상태로 저장되는 이진 검색 트리(binary search tree)의 형태로 요소를 저장한다. 또한 TreeSet 클래스는 Set 인터페이스를 구현하므로, 요소를 순서에 상관없이 저장하고 중복된 값은 저장하지 않는다.
TreeSet 클래스를 이용한다면 위 소스처럼 map.containsKey를 통해 중복을 확인하고, 우선순위 큐를 통해 정렬할 필요가 없음을 배웠다.

TreeSet<String> set = new TreeSet<String>(new Comparator<String>() {
				@Override
				public int compare(String o1, String o2) {
					return o2.compareTo(o1); // o2-o1
				}
			});

2. 'F12'는 16진수로써만 '12F'보다 클 뿐 아니라, 문자열로도 크기때문에 10진수로 변환이후 정렬 할 필요없이 문자열로 정렬이후 필요한 순번의 16진수만 10진수로 변환해도 된다.

// 'F12'가  '12F'보다 아스키코드값이 크다
// 그러므로 정수변환해서 넣을 필요 없다. 
	set.add(s);

위와같이 10진수로 변환하는 작업을 최소화해 효율을 높일 수 있다.

3. Integer.parseInt(s, 16) Integer에 16진수를 10진수로 변환해주는 메소드가 있다. 하하하하