[SWEA / Java] 5658번: [모의 SW 역량테스트] 보물상자 비밀번호

문제 풀이 날짜: 2023.10.05
포스트 작성일: 2023.10.05

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

SWEA 5658번: [모의 SW 역량테스트] 보물상자 비밀번호

 

키워드

시뮬레이션, 배열

 

풀이 접근법

• 보물 상자에 적힌 숫자로 만들 수 있는 모든 수 중, K번째로 큰 수를 구하기
  • 각 변에 있는 세 자리 문자를 조합하면 16진수 수가 하나 나온다. (예: B3B)
  • 그런데 상자의 변이 총 4개이므로 한 회전당 4가지 16진수가 나온다. (1B3, B3B, 81F, 75E)
  • 그리고 이것을 0, 1, 2, ..., N / 4 - 1 회전시킬 수 있으므로 최대 ( N / 4 - 1) * 4 = N - 4가지 16진수를 얻을 수 있다.
  • 이 중 K번째로 큰 수를 찾으면 된다. 중복되는 수는 반드시 제거해야 하므로 주의한다.
  • 16진수의 정수로의 변환은 Integer.parseInt("변환할 16진수", 16)를 쓰면 된다.
• 상자의 회전은 어떻게 구현할까?
  • 회전에 따른 인덱스 처리가 중요하다.
  • 비밀번호를 만들 시작점 pos를 정의해서 한 칸 씩 밀어주고, 인덱스 범위를 넘긴다면 나머지를 구해서 보정해주었다.
• 정렬과 중복 제거는 TreeSet을 쓰면 좋다. add한 값 중 중복을 허용하지 않으면서 자동으로 정렬된 상태를 유지한다.

 

코드

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

public class Solution {

	private static int N;
	private static int K;
	
	private static TreeSet<Integer> set;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());
		
		StringBuilder sb = new StringBuilder();
		for(int test_case = 1; test_case <= T; test_case++) {
			String[] temp = br.readLine().split(" ");
			set = new TreeSet<>(Collections.reverseOrder());
			
			N = Integer.parseInt(temp[0]);
			K = Integer.parseInt(temp[1]);
			
			String input = br.readLine();
			makePassword(input);

			Object[] result = set.toArray();
			int answer = (int) result[K - 1];
			
			sb.append("#").append(test_case).append(" ").append(answer).append("\n");
		}
		
		System.out.print(sb);
	}

	private static void makePassword(String input) {
		int digit = (N / 4);
		
		int pos = 0; //원점에서 시작
		while(true) {
			int pwdCount = 0;
			for(int i = 0; i < 4; i++) { //네 변을 조사
				String pwd = "";
				int start = i * digit;
				for(int j = start ; j < start + digit; j++) { //(N / 4)자리 비밀번호 생성
					int idx = (pos + j) % N;
					pwd += input.charAt(idx);
				}
				int password = Integer.parseInt(pwd, 16);
				
				if(set.contains(password)) pwdCount++;
				
				set.add(password);
			}
			
			pos = ((pos - 1) + N) % N; //회전 후 탐색
			
			if(pwdCount == 4) { break; } // 네 변의 비밀번호 모두 이미 생성된 적 있다면
		}
	}

}

---

 

 

git 링크

(git 링크 첨부)