deque를 이용하면 회전이 가능하다 -보물상자 비밀번호-

1. 문제

 

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

 

SW Expert Academy

SW Expert Academy

 

16진수의 배열이 주어지고, 사각형의 각 변에 동일한 개수만큼 수들이 놓여있다.

 

그러한 개수만큼 모아 비밀번호를 만들고, 이들을 1회전씩 수행하면서 비밀번호를 계속 생성해나간다

 

k번째로 큰 비밀번호를 찾는다면?

 

 

2. 풀이

 

SWEA의 A형 수준? SW 역량테스트는 결국 문제에서 요구하는대로 성실하게 구현하면 되는 것 같다

 

대부분 구현, 완전탐색, 시뮬레이션 이런 느낌?

 

먼저 사각형의 각 변에 동일한 개수만큼 숫자가 놓여있으며, 회전해야하므로 rotate()를 이용하기 위해 deque를 이용하자

 

사각형의 각 변의 개수는 n//4로 구할 수 있을 것

 

T = int(input())

for t in range(1,T+1):

    n,k = map(int,input().split())

    a = n//4

    queue = deque(list(input()))

    password_set = set()

 

중복을 제거하는데 유용한 set()을 미리 만들어두자고

 

deque를 순회하면서 각 변의 길이만큼 순회하면 그것들을 하나로 모아 16진수 문자열로 만든다

 

나중에 크기순으로 정렬하기 위해 16진수 문자열을 10진수 값으로 바꿔준다

 

def get_num(n,len_n,key_dict):
    
    ans = 0

    for i in range(len_n-1,-1,-1):
        
        key = key_dict.get(n[i],0)

        if key == 0:
        
            ans += (int(n[i])*(16**(len_n-1-i)))
        
        else:
            
            ans += key*(16**(len_n-1-i))
    
    return ans
        


key_dict = {'A':10, 'B':11, 'C':12, 'D':13, 'E':14, 'F':15}

 

16진수를 10진수로 어떻게 바꾼대???

 

내장함수가 아마 있겠지만.. 구현하는데 집중하는걸로 해보면

 

맨 뒷자리부터 0의 자리, 16의 자리, 16^2의 자리, 16^3의 자리,...일테니까

 

뒷자리부터 한자리씩 읽어와 해당하는 정수값에 16^n을 곱해주면서 더해나가면 10진수로 될것

 

A,B,C,D,E,F는 10,11,12,13,14,15에 대응되도록 미리 사전을 만들고

 

 

deque의 회전 수를 r = 0이라고 한다면.. 1회전에 1칸씩 움직인다고 나와있다

 

한변의 길이만큼 회전하면, 첫 상태와 동일한 비밀번호들을 생성한다. 

 

한변의 길이가 하나의 주기가 된다는 소리

 

while r != a:

    cnt = 0

    ans = ''

    for b in queue:

        ans += str(b)

        cnt += 1

        if cnt == a:

            transform_ans = get_num(ans,a,key_dict)

            password_set.add(transform_ans)

            cnt = 0

            ans = ''


    queue.rotate(1)

    r += 1

 

중복되는 번호가 안들어가도록 set()을 이용해서 중복처리를 해주자

 

 

from collections import deque

def get_num(n,len_n,key_dict):
    
    ans = 0

    for i in range(len_n-1,-1,-1):
        
        key = key_dict.get(n[i],0)

        if key == 0:
        
            ans += (int(n[i])*(16**(len_n-1-i)))
        
        else:
            
            ans += key*(16**(len_n-1-i))
    
    return ans
        


key_dict = {'A':10, 'B':11, 'C':12, 'D':13, 'E':14, 'F':15}


T = int(input())

for t in range(1,T+1):

    n,k = map(int,input().split())

    a = n//4

    queue = deque(list(input()))

    password_set = set()

    r = 0

    while r != a:
        
        cnt = 0

        ans = ''

        for b in queue:
            
            ans += str(b)

            cnt += 1

            if cnt == a:
                
                transform_ans = get_num(ans,a,key_dict)
                
                password_set.add(transform_ans)
                
                cnt = 0

                ans = ''
        
        
        queue.rotate(1)

        r += 1
    

    password = sorted(list(password_set),reverse=True)

    print('#'+str(t),password[k-1])

 

아무튼 모든 처리를 한 password_set을 오름차순 정렬하고 k번째 수를 출력하면 정답

 

0부터 시작하니까 k-1번을 출력해야겠지

 

 

4. 되돌아보기

 

깔끔하게 잘 푼것 같다

 

많이 풀어본건 아닌데 몇문제 경험해본 결과 성실하게 문제에서 요구한 그대로 구현하면 되는 것 같다

 

엄청난 알고리즘을 요구하는건 아니고 구현, 시뮬레이션, 완전탐색 등등

 

근데 대신에 엄청 복잡하게 만들어서 구현하기 쉽지 않도록 만드는게 특징인듯

 

아무튼 그러니까 자신감 갖자고