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

1. 문제분석

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRUN9KfZ8DFAUo 

SW Expert Academy

4변에 16진수가 적힌 보물상자가 있다. 변을 시계방향으로 한 칸 옮길 수 있고 이때 사각형에 각 변은 비밀번호가 된다.

주어진 K번째 큰 수를 10진수로 만들어 반환하는 문제다.

 

규칙을 보면 각 변을 스타트로 한다음 각변의 암호 개수(75E면 3개)만큼 돌아가면 다시 자기 자신이 돌아온다.

결국 답은 각 변의 암호개수만큼 돌리고 맨 마지막 수가 맨 처음으로 가면 된다.

2. 시행착오

필자는 처음에 위와 같이 구현했었다. 하지만 인덱스 오류가 나오고 문제를 잘못이해한 것 같았다.

각 변이 여러 숫자로 배치 가능하고 그 때 돌리는 줄 알고 nP(한변에서의 암호 개수)를 진행하고 구했다.

결과는 당연히 시간초과였다.

 

생각해보니 예제만 보고 돌리는 횟수를 3으로 고정시켜놨다.

한변의 암호 개수만큼 돌려야했는데 결국 딱 한줄만 수정했더니 문제가 풀렸다.

3. 구현

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

public class Solution {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        for (int c = 1; c <= tc; c++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int size = Integer.parseInt(st.nextToken());
            int divPos = size / 4;
            int maxPos = Integer.parseInt(st.nextToken());

            char[] arr = br.readLine().toCharArray();

            ArrayList<Character> list = new ArrayList<>();
            ArrayList<Long> numList = new ArrayList<>();

            //문자를 리스트에 저장
            for (char input : arr) {
                list.add(input);
            }

            //모든 값은 3번은 돌아야 한다.
            for (int k = 1; k <= divPos; k++) {
                //4개씩 끊어서 값 가져오기(사분면)
                int pos = 0;
                for (int i = 1; i <= 4; i++) {
                    String data = "";
                    //16진수 생성
                    for (int j = 0; j < divPos; j++) {
                        data += list.get(pos++);
                    }
                    //생성된 16진수를 저장
                    Long value = Long.parseLong(data, 16);
                    if(!numList.contains(value)){
                        numList.add(value);
                    }
                }
                list.add(0, list.get(list.size() - 1));
                list.remove(list.size() - 1);
            }
            numList.sort(Collections.reverseOrder());
            System.out.println("#" + c + " " + numList.get(maxPos - 1));
        }
    }
}

어차피 사각형이 고정이므로 돌려야하는 횟수를 전체 크기에서 4를 나눈수로 초기화 했다.

list는 문자의 형태와 순서를 가진 리스트, numList는 나온 암호를 16진수에서 10진수로 변환하는 리스트다.

 

for문 첫번째는 몇개를 돌리는지다. 각변의 암호 개수만큼 돌리면된다.

for문 두번째는 각 변을 구하기 위한 것이다.

마지막 for문은 변에 있는 암호 개수만큼 이어서 16진수를 만들어 낸다.

 

마지막 for문을 벗어나고 16진수에서 10진수로 변환 후 리스트에 저장했다.

중복이 되면 안되니 contains를 통해 중복체크를 했다.

 

이 문제는 TreeSet, PriorityQueue로 구하면 더 쉽게 할 수 있을 것 같다.

필자는 list로 했지만 다른 것도 충분히 구현가능하다.

4. 마무리

문제는 엄청 쉬웠는데 새벽 4시에 정신없이 풀었더니 답이 안보였다.

결국 순열로 하다가 짜증나서 오늘 다시 풀었는데 너무 허무한 문제..