[240313] 파이썬: 코드카타 40

[파이썬 코드카타]

3진법 뒤집기

https://school.programmers.co.kr/learn/courses/30/lessons/68935

 

1) 어떤 문제가 있었나: N진법 개념을 몰라서 공부해봄 

- 문제: 자연수 n을 3진법 상에서 앞뒤로 뒤집은 후, 이를 다시 10진법으로 표현한 수를 반환

 

① N진법의 의미

- 진법이란? 수를 셀 때, 자릿수가 올라가는 단위를 기준으로 하는 셈법의 총칭. 수를 표기하는 기수법 중 하나

- 표기에 사용되는 수의 개수에 따라 N진법으로 이름이 붙음

 └ 일반적으로 사용하는 0 1 2 3 4 5 6 7 8 9 로 이뤄진, 10개 문자를 이뤄진 표기법이 바로 10진법 (ex 34,205 등)  

 └ 컴퓨터 공항에서 주로 쓰이는 2진법에서는 숫자 표기에 0, 1만 사용

- 숫자의 밑(base)에 각 진법에 해당되는 숫자를 적어서 표기 (ex. 2진법: 101011₂ , 10진법: 34,215₁₀ 등) 

 

② 10진법 계산하는 법 

34,215

= 30,000  +  4,000  +  200 + 10 + 5 

= 3 * 10⁴ + 4 * 10³ + 2 * 10²  + 1 * 10¹  + 5 * 10⁰

 

▽ 식으로 표현한 경우 

③ N진법 계산 응용

- N진법은 첫째 자릿수(오른쪽)부터 0, 1, 2 제곱을, 즉 N^자릿수을 해주면 됨  

a*N^b

 (a는 각 자리에 위치한 상수, b는 자릿수(0부터시작), N은 진법)

 

- 2진법 예시:

101011₂

= 1* 2⁵ + 1* 2³ + 1* 2¹ + 1* 2⁰

= 32 + 8 + 2 +1 

= 43₁₀

 

③ 10진법 > N진법으로 변환

- 10진법 숫자를 N으로 나눠 나머지 값을 구하기를 반복 > 맨 마지막에 나온 나머지 값부터 앞에 배열하면 완료 

 

2) 내가 시도해본 건 무엇인가

- N집법을 구하는 것에 대해서 순서 대로 정리 해봄

- 첫 번째 시도: 주어진 n값은 고정하고 3의 제곱값을 늘려서 나머지 값을 추출하면 어떨까?
# 45 / 3**1 = 15 #0 
# 45 / 3**2 = 5  #0
# 45 / 3**3 = 1.6 #18 #1

(결과) 분모의 크기가 달라 나머지 값이 다르게 나와서 실패 

 

- 재시도 

[코드 순서]

① n값을 3으로 나눠서 나온 값의 리스트를 뽑는 함수가 필요. list = [45, 15, 5, 1.6]
② 3을 나눈 값 리스트에서 원소를 하나씩 뺀 다음 3을 나눈 나머지와 마지막 몫을 자리에 맞게 배치

③ 3진법으로 숫자를 다시 10진법으로 표현 

 

- n=125인 경우에서 실패

#n=45일 때를 기준으로 작성 

def solution(n):
    answer = 0
    result = 0
    list = []
    list_length = [] 

    for i in range(n):
        if (n / 3**i) > 3: 
            list.append(n / 3 ** i)  # list = [45.0, 15.0, 5.0]

    for j, k in zip(list, range(len(list))):   #j, k = [(45, 0), (15,1), (5, 2)]
        if k == 0:
        	#맨 오른쪽 - 첫째 자리수(K==0)는 나머지만 45%3
            answer = int(j % 3) #첫째 자리수(K==0)는 나머지만 45%3
        else:
        	#둘째 자리수부터는 10의 제곱 곱해서 자리수 만들기 
            answer = int(answer + (j % 3)*10**k)  
        
            if j / 3 < 3:
            	#맨 왼쪽 - 앞자리수는 몫을 앞에 넣기
                #3으로 더이상 나눌 수 없는 경우에 해당 
                answer = int( answer + (j // 3)*10**(k+1) ) 
	
    # 숫자 뒤집기는 pass #10진법으로 다시 바꿀 때, 뒤에 숫자부터 들어가니까 
    # reversed_answer = str(answer)[::-1] #숫자 뒤집기는 pass  #'0021'
    
    #answer 값을 하나씩 빼기 위해 str 처리 
    str_answer = str(answer) #'1200'
    for r in range(len(str_answer)): # r =[0, 1, 2, 3] 
        result = result + (int(str_answer[r])*3**r)

    return result

 

- 나머지(%)와 몫(// )을 구한뒤 소수점 처리 되었는데 10의 제곱을 곱하면서 전체 값이 틀림  > 나머지(%)와 몫(// ) 부분에 int 상수처리를 해주고 재시도 하였으나 정확성 30점으로 또 실패 

def solution(n):
    answer = 0
    result = 0
    list = []
    list_length = [] 

    for i in range(n):
        if (n / 3**i) > 3: 
            list.append(n / 3 ** i)  # list = [45.0, 15.0, 5.0]

    for j, k in zip(list, range(len(list))):   #45, 0 / 15,1 / 5/2
        if k == 0:
            answer = int(j % 3) # 첫째 자리수는 나머지만 45%3
        else:
            answer = answer + int(j % 3)*10**k  # 두번째자리수부터는 10의 제곱처리 
            if j / 3 < 3:
                answer = int( answer + int(j // 3)*10**(k+1) ) #마지막 3으로 더이상 나눌 수 없으면 몫을 앞에 넣기

    # reversed_answer = str(answer)[::-1] #숫자 뒤집기 #'0021'
    str_answer = str(answer) #'1200'
    for r in range(len(str_answer)): # 0 1 2 3 
        result = result + (int(str_answer[r])*3**r)

    return result

 

3) 어떻게 해결했나

- 도저히 모르겠어서, 결국 다른 사람 풀이를 보고 진법과 관련한 내장함수 추가 공부  

def solution(n):
    answer = ""  #빈 문자열 준비
    while n > 0:   #while로 n이 0 미만일 때까지 반복 설정 
        answer = answer + str(n % 3)   #n%3(나머지값)을 문자열로 해서 answer에 더하기 
        n = n // 3 #n을 3으로 나눌 때 마다 나오는 몫을 n에 새롭게 지정 > while식 n 값이 적어짐 

    answer = int(answer, 3)
    return answer

4) 무엇을 새롭게 알았나

① int()

- int(x) : 문자열 혹인 실수 형태의 값을 정수로 반환하는 함수. 실수일 경우 버림처리 

# 문자열
int('3') # 3
int('3.5') # error

#실수
int(3.1) # 3
int(3.96556) # 3

 

- int(x, N): 문자열 x를 N진수로 변환 후 반환!  > 처음 알게된 사실 

int('1332', 4) #126
int('12201', 3) #154

 

② while

- while은 특정 조건이 만족되기까지 계속 반복되는 함수라는 것을 알고 있었으나 활용 방식을 제대로 이해못함

- 만약 while n > 0 과 같은 조건이 있다면, while이 반복되는 과정에서 n이 0 이하가 되어 멈출 수 있는 식이 필요함

- 본 문제에서는 n = n // 3 조건을 통해 n을 3으로 나눴을 때 몫을 n변수로 새롭게 지정해서 값을 줄여나감 

n = 45
answer = []

while n > 0:
	answer.append(n)
	n = n // 3
answer # [45, 15, 5, 1]

 

③ divmod()  

- 두 개의 숫자를 인자로 받아, 첫 번째 숫자를 두 번째 숫자로 나눈 몫과 나머지를 튜플(tuple) 형태로 반환

divmod(x, y) = (x // y, x % y)

#예시 
divmod(3, 8) #(0, 3) 

3//8 == 0
3 % 8 == 3

 

- divmod()를 활용한 다른 사람 문제 풀이 

└ n 조건을 3이상으로 해서 마지막 몫은 별도 추가 함 

arr=[]
while n >= 3:
    n,r = divmod(n, 3) #n은 나누기의 몫, r은 나머지 
    arr.append(r)   # 나머지는 리스트에 넣고, 3으로 나눈 몫 n은 다시 while로 
arr.append(n)     # n을 3으로 나눌 수 있는 마지막 숫자의 몫은 마지막으로 추가 
print(arr) #[0, 0, 2, 1]

# map 복습: map(함수명, 함수를 적용할 iterator)
# join 복습: 구분자.join(리스트) / 각 리스트에 있는 문자열을 하나로 합쳐줌
# arr 각각 요소가 str 문자열이 되도록 한뒤, 
answer = ''.join(map(str,arr))

answer = int(answer,3)

 

└ while의 n 조건을 0 이상으로하므로, 나머지값(mod)만 리스트에 추가해도 됨  

n = 45
#3진법으로 변환 과정(뒤집힌 순으로 되어있음)
rev_base = []
while n > 0:
    n, mod = divmod(n, 3)
    rev_base.append(mod)
print(rev_base) # [0, 0, 2, 1]

answer=0
for i in range(len(rev_base)):
    answer+=(3**i)*rev_base[::-1][i]
    # rev_base[::-1] 이 리스트 순서를 거꾸로 한 것 
    # [1, 2, 0, 0]으로 리스트를 바꿔서, 10진법으로 바꾸는 계산 적용
answer