프로그래머스 n진수 게임

 

2018 KAKAO BLIND RECRUITMENT 3차 문제입니다.

 

문제 풀이

1. 0부터 차례대로 n진수로 변환합니다.

2. n진수로 변환한 수를 q에 넣어줍니다.

3. q에 들어간 요소의 수가 게임 참가자의 수 m보다 크게되면 answer에 큐의 p번째 요소(튜브의 순서)를 넣어주고 q에서 m개의 요소를 제거하여 줍니다.

4. 1 ~3의 과정을 answer의 길이가 t가 될 때까지 반복해줍니다.

 

* 단계1에서 0부터 계속 n진수로 바꾸는 것을, 0에 계속 1씩 더해가는 방식으로 수정하면 더 빠를 것 같습니다.

Python Code

from collections import deque
T = "0123456789ABCDEF"
 
def convert(n, base):
    q, r = divmod(n, base)
    if q == 0:
        return T[r]
    else:
        return convert(q, base) + T[r]
 
def solution(n, t, m, p):
    q= deque()
    answer = ''
    
    #말해야할 숫자
    i = 0
    while len(answer) < t:
        c = convert(i,n)
        
        for s in list(c):
            q.append(s)
            
        while len(q) > m:
            answer+= q[p-1]
            for _ in range(m):
                q.popleft()
        i += 1
    return answer

Line 4 : 숫자 n을 base 진수로 변환시켜주는 함수입니다. 재귀식으로 수행됩니다.

결과

 

테스트 20 〉	통과 (2.07ms, 10.1MB)
테스트 21 〉	통과 (8.82ms, 10.2MB)
테스트 22 〉	통과 (4.58ms, 10.2MB)
테스트 23 〉	통과 (12.77ms, 10.2MB)
테스트 24 〉	통과 (20.17ms, 10.2MB)
테스트 25 〉	통과 (15.09ms, 10.2MB)
테스트 26 〉	통과 (5.53ms, 10.3MB)

두번째 풀이

위의 풀이에 *로 써놓은 것을 구현한 코드입니다.

Python Code

from collections import deque
 
class Num():
    def __init__(self, base):
        self.num = [0]
        self.T = list("0123456789ABCDEF")
        self.base = base
    def add(self):
        self.addOne(1)
    def addOne(self,depth):
        if depth > len(self.num):
            self.num = [1] + self.num
            return ;
        if self.num[-depth] == self.base-1:
            self.num[-depth] = 0
            self.addOne(depth+1)
        else:
            self.num[-depth] += 1
    def getNum(self):
        return [self.T[x] for x in self.num]
    
def solution(n, t, m, p):
    q= deque()
    answer = ''
    
    #말해야할 숫자
    num = Num(n)
    while len(answer) < t:
        
        for s in num.getNum():
            q.append(s)
            
        while len(q) > m:
            answer+= q[p-1]
            for _ in range(m):
                q.popleft()
        num.add()
    return answer

 

Line 3: Num 클래스는 n진수이며 처음에  num 변수는 [0]로 초기화됩니다.

Line 8 : Num 클래스의 add 메소드는 num 변수에 1을 더하는 메소드로 addNum이라는 메소드를 통해 실행됩니다.

Line 10 : addNum은 depth 자릿수의 숫자에 1을 더하는 것으로, 수가 가득차는 경우(10진수의 경우 9에 1을 더해 10이 되는 경우)에는 depth 자릿수의 숫자는 0으로 하고 depth+1번째 자릿수에 1을 더하게 됩니다.

결과

테스트 20 〉	통과 (2.17ms, 10.3MB)
테스트 21 〉	통과 (8.86ms, 10.4MB)
테스트 22 〉	통과 (4.44ms, 10.2MB)
테스트 23 〉	통과 (11.55ms, 10.2MB)
테스트 24 〉	통과 (14.63ms, 10.3MB)
테스트 25 〉	통과 (11.84ms, 10.3MB)
테스트 26 〉	통과 (6.06ms, 10.3MB)

테스트 24번을 기준으로 앞의 풀이보다 약 5ms 빨라진 것을 볼 수 있습니다.

문제 링크

코딩테스트 연습 - [3차] n진수 게임