프로그래머스_3진법 뒤집기_210718_02

프로그래머스 코딩 테스트입니다. 파이썬으로 작성했고 Level_01 입니다.

진법에 대해서 이해가 필요한 문제입니다.

주피터 노트북 마크다운 셀에 진법에 대한 설명과 여러 표현법에 대해서 적었습니다.

코드를 3가지 방법으로 나타냈습니다.

 

<문제 : https://programmers.co.kr/learn/courses/30/lessons/68935>

In [ ]:

문제 : 3진법 뒤집기¶

문제 설명¶

• 자연수 n이 매개변수로 주어집니다. n을 3진법 상에서 앞뒤로 뒤집은 후, 이를 다시 10진법으로 표현한 수를 return 하도록 solution 함수를 완성해주세요.

제한사항¶

• n은 1 이상 100,000,000 이하인 자연수입니다.

입출력 예¶

n	result
45	7
125	229

• 입출력 예 설명
  • 입출력 예 #1
    • 답을 도출하는 과정은 다음과 같습니다.
    • 7을 return 해야 합니다.

n (10진법)	n (3진법)	앞뒤 반전(3진법)	10진법으로 표현
45	1200	0021	7

• 입출력 예 #2
  • 답을 도출하는 과정은 다음과 같습니다.
  • 따라서 229를 return 해야 합니다.

n (10진법)	n (3진법)	앞뒤 반전(3진법)	10진법으로 표현
125	11122	22111	229

In [28]:

41//3

Out[28]:

13

알고리즙¶

• 3진수로 표현하기 ; n = 125
  • $125 = 1 \times 3^4 + 1 \times 3^3 + 1 \times 3^2 + 2 \times 3^1 + 2 \times 3^0$
  • 125 = 3 x 41 + 2 : 125%3=2(나머지), 125//3=41(몫)
  • 41 = 3 x 13 + 2 : 41%3=2(나머지), 41//3=13(몫)
  • 13 = 3 x 4 + 1 : 13%3=1(나머지), 13//3=4(몫)
  • 4 = 3 x 1 + 1 : 4%3=1(나머지), 4//3=1(몫)
  • 나머지들의 배열이 3진수로 표기되는 것과 같습니다. 위의 나열한 수식을 순환문으로 반복하여 3진수를 구합니다.

• 3진수 뒤집기
  • 순환문을 통해 3진수의 배열을 trit = []에 추가해서 저장했습니다.
  • trit : 3진수의 배열을 뒤집은 것입니다
  • trit = trit[::-1] : 리스트의 슬라이싱에서 '-1'은 역순으로 배열하는 것입니다.
    • 이렇게 하면 3진수 배열이 제대로 됩니다

• 10진수로 만들기
  • 3진수의 첫 번째 수가 뒤집어진 수의 $1 = 3^0$의 자리입니다.
  • 3진수의 두 번째 수가 뒤집어진 수의 $3 = 3^1$의 자리입니다.
  • 3진수의 세 번째 수가 뒤집어진 수의 $9 = 3^2$의 자리입니다.
  • 이것을 반복하면 뒤집어진 수를 10진수로 나타낸 것이 됩니다

삼진수 : Trit, Trinary digit¶

In [ ]:

In [32]:

n = 125
trit = []

if n < 3:
    trit = [n]
    print(n)

while True:
    r = n % 3
    trit.append(r)
    n = n // 3
    if n < 3:
        trit.append(n)
        break
        
trit

Out[32]:

[2, 2, 1, 1, 1]

In [33]:

trit = trit[::-1]
trit

Out[33]:

[1, 1, 1, 2, 2]

In [34]:

deci = 0
for i in range(len(trit)):
    deci += trit[i] * 3**i
    
deci

Out[34]:

229

In [ ]:

제출한 코드입니다.¶

In [19]:

def solution(n):
    trit = []
    
    if n < 3:
        trit = [n]
        return n

    while True:
        r = n % 3
        trit.append(r)
        n = n // 3
        if n < 3:
            trit.append(n)
            break
            
    trit = trit[::-1]
    
    deci = 0
    for i in range(len(trit)):
        deci += trit[i] * 3**i

    return deci

In [20]:

n = [45, 125]

for i in n:
    print(solution(i))

7
229

In [ ]:

3진수를 재배열하지 않고 결과물을 구할 수도 있습니다.¶

• 마지막 십진수를 계산할 때, 3의 지수를 변경하면 됩니다

In [39]:

def solution_desc(n):
    trit = []
    
    if n < 3:
        trit = [n]
        return n

    while True:
        r = n % 3
        trit.append(r)
        n = n // 3
        if n < 3:
            trit.append(n)
            break
    # trit : "앞뒤반전 3진수" 입니다
    deci = 0
    
    for i in range(len(trit)):
        deci += trit[i] * 3**(len(trit)-i-1)

    return deci

In [40]:

n = [45, 125]

for i in n:
    print(solution_desc(i))

7
229

In [ ]:

또 다른 방법입니다.¶

• $deci = (((2*3 + 2)*3 + 1)*3 + 1)*3 + 1$
• $deci = 2*3^4 + 2*3^3 + 1*3^2 + 1*3^1 + 1$
  • deci = 2 = trit[0]
  • deci = 2x3 + 2 = deci x 3 + trit[1]
  • deci = (2x3 + 2)x3 + 1 = deci x 3 + trit[2]
  • deci = ((2x3 + 2)x3 + 1)x3 + 1 = deci x 3 + trit[3]
  • deci = (((2x3 + 2)x3 + 1)x3 + 1)x3 + 1 = deci x 3 + trit[4]
• deci에 그 다음 자릿수를 더한 값에 계속 3을 곱해도 같은 결과입니다.

In [45]:

def solution_02(n):
    trit = []
    
    if n < 3:
        trit = [n]
        return n

    while True:
        r = n % 3
        trit.append(r)
        n = n // 3
        if n < 3:
            trit.append(n)
            break
            
    deci = trit[0]
    for i in range(1, len(trit)):
        deci = deci * 3 + trit[i]
        
    return deci

In [46]:

n = [45, 125]

for i in n:
    print(solution_02(i))

7
229

In [ ]: