[모의 SW 역량 테스트] 5658 보물상자 비밀번호 (Python)

출처

https://swexpertacademy.com/main/code/problem/problemDetail.do

문제

각 변에 다음과 같이 16진수 숫자(0~F)가 적혀 있는 보물상자가 있다.

보물 상자의 뚜껑은 시계방향으로 돌릴 수 있고, 한 번 돌릴 때마다 숫자가 시계방향으로 한 칸씩 회전한다.

 

각 변에는 동일한 개수의 숫자가 있고, 시계방향 순으로 높은 자리 숫자에 해당하며 하나의 수를 나타낸다.

예를 들어 [Fig.1]의 수는 1A3, B54, 8F9, D66이고, [Fig.2]의 수는 61A, 3B5, 48F, 9D6이다.

보물상자에는 자물쇠가 걸려있는데, 이 자물쇠의 비밀번호는 보물 상자에 적힌 숫자로 만들 수 있는 모든 수 중, K번째로 큰 수를 10진 수로 만든 수이다.

N개의 숫자가 입력으로 주어졌을 때, 보물상자의 비밀 번호를 출력하는 프로그램을 만들어보자.

(서로 다른 회전 횟수에서 동일한 수가 중복으로 생성될 수 있다. 크기 순서를 셀 때 같은 수를 중복으로 세지 않도록 주의한다.)

 

[제약 사항]
 

1. N은 4의 배수이고, 8이상 28이하의 정수이다. (8 ≤ N ≤ 28)       
2. N개의 숫자는 각각 0이상 F이하로 주어진다. (A~F는 알파벳 대문자로만 주어진다.)
3. K는 생성 가능한 수의 개수보다 크게 주어지지 않는다.

[예제]
 

아래와 같이 (1, B, 3, B, 3, B, 8, 1, F, 7, 5, E) 12개의 숫자가 주어지고 K가 10인 경우를 살펴보자.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

이 경우에 생성 가능한 수는 각 회전 별로 다음과 같다.  

0회전 : 1B3, B3B, 81F, 75E
1회전 : E1B, 3B3, B81, F75
2회전 : 5E1, B3B, 3B8, 1F7
3회전 : 0회전과 동일

생성 가능한 수를 내림 차순으로 나열하면 다음과 같고, K(=10)번째로 큰 수는 503(=1F7)이다.
(B3B를 중복으로 세지 않도록 주의한다.)

F75, E1B, B81, B3B, 81F, 75E, 5E1, 3B8, 3B3, 1F7, 1B3

 

[입력]

가장 첫 줄에는 테스트 케이스의 개수 T가 주어지고, 그 아래로 각 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 숫자의 개수 N과 크기 순서 K가 주어 진다.

그 다음 줄에는 16진수 0~F 숫자가 공백 없이 N개 주어진다.

 

[출력]

출력의 각 줄은 '#t'로 시작하고, 공백을 한 칸 둔 다음 정답을 출력한다.

(t는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)

 

5  // 테스트 케이스의 개수 T = 5 12 10  // 1번째 테스트 케이스, N=12, K=10 1B3B3B81F75E  // N개의 숫자 16 2  // 2번째 테스트 케이스, N=16, K=2 F53586D76286B2D8  // N개의 숫자 …  // 이하 sample_input.txt 참조

#1 503 #2 55541 #3 334454 #4 5667473 #5 182189737

풀이

뭔가 특별한 알고리즘을 써서 풀었다고 생각은 안들었다. 그냥 단순히 하라는대로 구현만 하니 풀리는 문제였다.

유의해야 할점을 꼽아보자면

•  사각형 한 변에 할당되는 번호의 개수 == 회전 수라는 점 
•  한 번 회전 할 때마다 번호의 끝자리가 맨 앞으로 오게 되는데 한 변에 할당된 개수만큼 회전하면 번호 배치가 동일해지게 되므로 더 회전을 할 이유가 없어진다.
• 중복이 존재하면 안된다. 중복을 없앨 방법으로서 중복을 허용하지 않는 자료구조인 set을 사용하였다.
• 16진수를 10진수로 변환하는 게 관건이었는데 int함수가 진법 변환이 가능하다는 것을 알게 되었다!
• int(x, base=10) 라는 구조로 되어있으며 10진수로 변환시키고 싶은 숫자를 "반드시" string으로 처리해 x 에 넣고 base에 진수를 넣어 사용함.

int형 진법 변환 예시

코드

T = int(input())
for t in range(T):
    N, K = map(int,input().split())
    pw = list(map(str,input()))
    cnt = N // 4 # 한 변당 번호 개수 = rotate수
    arr = [] # 회전 시킨 후 16진수 번호가 저장 될 리스트
    for i in range(cnt): # rotate 수 만큼 회전시킴
        pop = pw.pop() #리스트 끝 부분을 맨 앞으로 이동 시키면 한번 회전 완료됨
        pw.insert(0,pop)
        for j in range(0,N,cnt): # 리스트 내에서 각각 떨어져있는 요소를 하나의 번호로 합침 
            a = ''
            for k in range(j,j+cnt):
                a += pw[k]
            arr.append(a)
    new_arr = set(arr) # 중복을 허용치 않는 자료구조 set 활용
    answer = [] # 10진수로 변환된 숫자가 들어갈 리스트
    for num in new_arr: # 16진수 -> 10 진수로 변환
        answer.append(int(num,16))
    sorted_answer = sorted(answer,reverse=True) #내림차순 정렬
    print('#{} {}'.format(t+1,sorted_answer[K-1]))