[PS] n-th system game

Programmers: n-th system game

Conditions

{/* <!– - 진법 n, 미리 구할 숫자 갯수 t, 게임에 참가하는 인원 m, 순서 p가 주어진다.

• 말해야 하는 숫자 t개를 공백없이 차례로 문자열로 나타낸다.

• 1015는 각각 대문자 AF로 출력한다.

• 0부터 n진법으로 바꾸고, 그 값을 계속 이은 문자열을 만든다.

• t개를 말해야 하므로 game 문자열의 길이가 t * m + p보다 길면 n진법으로 바꾸는 과정을 멈춘다.

• answer의 길이가 t가 될 때까지 i * m + p번째 문자를 이어붙인다. –> */}

• The base n, the numbers to be obtained in advance t, the number of participants in the game m, and the sequence p are given.

• The number t that must be spoken is displayed in sequence without spaces.

• 10~15 are printed as capital letters A~F respectively.

• Changes from 0 to n base and creates a string that continues with the value.

• Since t is required, if the length of the game string is longer that $$ t \times m + p $$, the process of converting to n base stops.

• The $$ i \times m + p $$ -th character is concatenated until the length of answer becomes t.

Brute force

 1def solution(n, t, m, p):
 2    answer = ''
 3    num = 0
 4    game = ""
 5
 6    while True:
 7        numToN = convertN(num, n)
 8        game += numToN
 9
10        if len(game) > (t * m + p):
11            break
12
13        num += 1
14
15    for i in range(len(game)):
16        if i % m == p - 1:
17            answer += game[i]
18
19        if len(answer) == t:
20            break
21
22    return answer
23
24def convertN(num, n):
25    if num == 0:
26        return '0'
27
28    digit = "0123456789ABCDEF"
29    temp = ""
30
31    while num:
32        q, r = divmod(num, n)
33        temp = digit[r] + temp
34        num = q
35
36    return temp

{/_ _/}

• Max: Test 16 〉 Pass (37.41ms, 10.7MB)

Big-O notation

{/* <!– - convertN()에서 while문은 $$ log_n\ num $$번 반복하게 된다. 이것을 확장하면 convertN()은 $$ O(log\ num) $$이다.

• 다만, convertN()에 필요한 실제 시간은 num이 0일 때 1, 1일 때 1, 2일 때 1, 3일 때 2, 4일 때 2 … 이런 식으로 logscale로 증가하므로 while문에 걸리는 시간은 이 값을 합한 값이고, $$ 1+2+3+4+…+n $$인 $$ \frac{n(n+1)}{2} $$보다는 작을 것이므로 대략 $$ O(NlogN) $$에 가까울 것이다.

• answer를 만드는 for문은 $$ O(t) $$만큼 동작한다.

• 결과적으로, $$ O(NlogN) $$ 시간에 동작한다. –> */}

• In convertN(), the while statement is repeated $$ log_n\ num $$ times. Expanding this, convertN() is $$ O(log\ num) $$.

• However, the actual time required for convertN() is 1 when num is 0, 1 when 1, 1 when 2, 2 when 3, 2 when 4 … increases in logscale in this way. Therefore, the time taken for the while statement is the sum of these values. It will be less than $$ 1+2+3+4+…+n = \frac{n(n+1)}{2} $$, so it will be roughly close to $$ O(NlogN) $$.

• The for statement that makes answer works as much as $$ O(t) $$.

• As a result, it operates at $$ O(NlogN) $$ time.

Optimization

 1def convertN(num, n):
 2    if num == 0:
 3        return '0'
 4
 5    digit = "0123456789ABCDEF"
 6    temp = ""
 7
 8    while num:
 9        num, r = divmod(num, n)
10        temp = digit[r] + temp
11
12    return temp

{/_ _/}

• It’s a small difference, but don’t have to use q.

 1def solution(n, t, m, p):
 2    answer = ''
 3    num = 0
 4    game = ""
 5    targetLen = t * m + p
 6
 7    while len(game) < targetLen:
 8        game += convertN(num, n)
 9        num += 1
10
11    for i in range(len(game)):
12        if i % m == p - 1:
13            answer += game[i]
14
15        if len(answer) == t:
16            break
17
18    return answer

{/* <!– - numToN 변수도 안 써도 돼서 제거.

• t * m + p도 매 번 연산할 필요가 없다.

• while문 조건을 바꿔버리면 if문도 뺄 수 있다.

• 복잡하지 않은 문제라서 이 정도가 최대인 것 같다. –> */}

• Removed numToN because it is not necessary to use it.

• Even $$ t \times m + p $$ does not need to be calculated every time.

• If you change the condition of the while statement, you can also remove the if statement.

{/_ _/}

• Max: Test 15 〉 Pass (36.15ms, 10.9MB)

Remember

{/* <!– - 진법 변환하는 방법 기억해두면 좋을 것 같다.

• divmod(a, b)에서 a가 0일 때 q가 아무것도 반환되지 않았다. 주의. –> */}

• It would be good to remember how to convert the base system.

• In divmod(a, b), when a is 0, q was not returned. Caution.