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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
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
|
cs |
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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
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
|
cs |
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진수 게임
N진수 게임 튜브가 활동하는 코딩 동아리에서는 전통적으로 해오는 게임이 있다. 이 게임은 여러 사람이 둥글게 앉아서 숫자를 하나씩 차례대로 말하는 게임인데, 규칙은 다음과 같다. 숫자를 0
programmers.co.kr
'알고리즘 > 프로그래머스' 카테고리의 다른 글
| 프로그래머스 캐시 (0) | 2020.12.01 |
|---|---|
| 프로그래머스 튜플 (0) | 2020.11.30 |
| 프로그래머스 SQL 동명 동물 수 찾기 (0) | 2020.11.09 |
| 프로그래머스 SQL 우유와 요거트가 담긴 장바구니 (0) | 2020.11.09 |
| 프로그래머스 문자열 압축 (0) | 2020.11.09 |