[이것이 취업을 위한 코딩 테스트다 with 파이썬] 1이 될 때까지

첫 번째 나의 풀이 !

 

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

# 1, n에서 1을 뺀다.  2, n을 k로 나눈다.

result = 0

# *** 첫 풀이 ***
while n!=1:
    if n%k==0:
        n//=k
        result+=1
    else:
        n-=1
        result+=1
print(result)

 

책의 해설 본 후 나의 풀이

 

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

# 1, n에서 1을 뺀다.  2, n을 k로 나눈다.
result = 0

while True:
    target = (n//k) *k
    result += (n - target) # result에 더해진 값은 -1을 한 횟수가 더해진다
    n = target # 위 라인에서 -1하는 [1] 식을 수행 해준거이므로 k로 나누어 떨어지는 값으로 n을 다시 할당한다
    if n<k:
        print(n,k)
        break
    n//=k
    result+=1 # n이 k보다 작지 않다면 n을 k로 나누는 [2] 식을 수행하고 result에 +1을 카운트 해준다.
result+=(n-1) # n이 1이 될 때까지 빼줘야하므로 n과 1과의 차이를 result에 더해준다. 즉 n - |1| 이란 말이다.
print(result)

나의 원래 풀이는 n이 k로 나누어 떨어지지 않을때 while문을 계속 돌면서 result가 카운트된다.

하지만 두번째 풀이는 n이 k로 나누어 떨어질때의 값과 나누어 떨어지지 않을때의 n값의 차이를 통해 result에 카운트 해준다.

이 방법에서 큰 깨달음을 얻었다. 

엄청 큰 수의 경우라면 매우 이 방법이 효율성이 좋을것이고 많은 반복문을 돌지 않아도 바로 해당 횟수를 한번에 카운트를 할 수 있다는 점이 큰 장점이었다.

 

그리고 result+=(n-1)부분을 처음에 이해하기 어려웠는데 조금만 생각을 바꾸면 이해가 가능했다.

문제가 n을 1로 만드는 최소 횟수를 구해야한다.

그래서 위 while문에서 break되서 나온 n과 1의 차이값을 result에 카운트 해주는 것이다. 이는 n이 1로 되기 위해 1을 빼는 작업의 횟수를 한번에 카운트 하는 것이다.