[프로그래머스] n진수 게임

문제 출처: 프로그래머스 (https://school.programmers.co.kr/learn/courses/30/lessons/17687)

 

문제 설명

🔎튜브가 활동하는 코딩 동아리에서는 전통적으로 해오는 게임이 있다. 이 게임은 여러 사람이 둥글게 앉아서 숫자를 하나씩 차례대로 말하는 게임인데, 규칙은 다음과 같다.

숫자를 0부터 시작해서 차례대로 말한다.
첫 번째 사람은 0, 두 번째 사람은 1, … 열 번째 사람은 9를 말한다.
10 이상의 숫자부터는 한 자리씩 끊어서 말한다. 즉 열한 번째 사람은 10의 첫 자리인 1, 열두 번째 사람은 둘째 자리인 0을 말한다.
이렇게 게임을 진행할 경우,0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, …순으로 숫자를 말하면 된다.

한편 코딩 동아리 일원들은 컴퓨터를 다루는 사람답게 이진수로 이 게임을 진행하기도 하는데, 이 경우에는0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, …순으로 숫자를 말하면 된다.

이진수로 진행하는 게임에 익숙해져 질려가던 사람들은 좀 더 난이도를 높이기 위해 이진법에서 십육진법까지 모든 진법으로 게임을 진행해보기로 했다. 숫자 게임이 익숙하지 않은 튜브는 게임에 져서 벌칙을 받는 굴욕을 피하기 위해, 자신이 말해야 하는 숫자를 스마트폰에 미리 출력해주는 프로그램을 만들려고 한다. 튜브의 프로그램을 구현하라.

(별 희한한 동아리가 다 있다.)

나는 진법 변환을 남들보다 어렵게 푸는 경향이 있어 어렵게 느껴졌던 문제였다.

 

처음 접근 방식은 전체 사람 수 만큼 돌 때 진행되는 길이에서 p번째 수를 추출하는 방법이었다.

이런 접근은 진법이 고정되어있으면 해볼만한 시도였지만, n에 따라 전체 사람 수 만큼 돌 때 진행되는 수(10진수)가 달랐기 때문에 구현을 제대로 해보지도 못했다.

 

정답률이 56%나 되고, 질문도 별로 없었던 문제인데 고집 때문에 차마 구글에 검색하지는 못하고 그나마 있는 질문들에서 정보를 캐내 다음과 같은 풀이 방법으로 문제를 해결할 수 있었다.

 

<정답코드>

# 진법 변환기
def change(n: int, num: int) -> str:
    result = ''
    while num:
        num, mod = num//n, num%n
        if 9 < mod:
            mod = chr(mod+ord('A')-10)
        result += str(mod)
    
    return result[-1::-1]

def solution(n, t, m, p):
    total = t*m
    cur = '0'
    nx = 1
    
    while len(cur) < total:
        cur += change(n, nx)
        nx += 1
    
    return cur[p-1:(t-1)*m+p:m]

접근은 처음 생각했던 것과 크게 다르진 않다.

1. 숫자를 말하는 전체 횟수는 t*m이다.

2. 따라서, 현재 진행되고 있는 숫자를 문자열로 치환한 것을 현재까지 얘기한 숫자(문자형)에 더한다.

3. 해당 숫자(문자형)의 길이가 t*m이 되면 반복문을 탈출한다.

4. 발표 순서와 순환 수에 따라 문자열 slicing을 통해 정답을 도출한다.

 

처음 생각한 것과 가장 큰 차이점은 매번 p번째를 도출할 필요가 없어, 매번 문자열을 잘라 생각할 필요가 없다는 것이다. (해당 문제는 문자열 slicing을 통해 해결이 가능했다.)

 

그리고 while을 탈출할 기준을 진법에 따라 정할 필요가 없고 길이로 보면 간단한 것을 너무 어렵게 생각했던게 이번 문제에 고전했던 이유였던 것 같다.