[Algorithm] [Python] Programmers - 124 나라의 숫자

Programmers - 124 나라의 숫자

문제 설명

---

124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다.

• 124 나라에는 자연수만 존재합니다.
• 124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다.
  예를 들어서 124 나라에서 사용하는 숫자는 다음과 같이 변환됩니다.

 

자연수 n이 매개변수로 주어질 떄, n을 124 나라에서 사용하는 숫자로 바꾼 값을 return 하도록 solution 함수를 작성해 주세요.

제한사항

• n은 500,000,000 이하의 자연수 입니다.

제출 코드

1차 제출 코드

def solution(n):
    if n <= 3:
        return '124'[n-1]
    else:
        q, r = n // 3, n%3
        return solution(q) + '124'[r-1]

 

그냥 주어진 테케를 보고 직관적으로 생각난 방법을 코드로 옮겼다.

 

n이 3보다 작거나 같은 경우에는 '124'에서 해당 값-1 번쨰 원소를 반환한다.

 

n이 3보다 큰 경우에는 몫과 나머지를 구하고 이를 기반으로 답을 구하였다.

 

결과는 망했다.

 

위 코드는 주어진 테스트케이스는 만족하지만 중요한 한가지를 놓쳤다.

 

놓친것을 아래에 보완하여 제출한 결과 AC를 받을 수 있었다.

 

최종 제출 코드

def solution(n):
    if n <= 3:
        return '124'[n-1]
    else:
        q, r = n // 3, n % 3
        if r == 0:
            q -= 1
        return solution(q) + '124'[r-1]

 

풀이 해설

---

1차 제출 코드에서 n값을 9로 전달할 경우 정답은 '24'이지만 q=3, r=0이 되어 반환되는 문자열은 '44'다.

 

나머지가 0이 되는 경우를 생각하지 못했던 것이다. 모든 3의 배수 값을 인자로 전달받았을 때 적절한 문자열을 반환하지 못한다.

 

해당 예외사항을 처리해주기 위해 나머지가 0인 경우를 확인하여 몫 -= 1을 진행한 이후 문자열을 반환하였다.

 

다른 사람의 풀이

---

def solution(n):
    if n <= 3:
        return '124'[n-1]
    else:
        q, r = divmod(n-1, 3)
        return solution(q) + '124'[r]

divmod 함수를 이용하여 몫과 나머지를 깔끔하게 구해내셨다.

또한, 몫을 구할때는 전달받은 정수의 -1 값을 기준으로 몫을 구하여 예외의 경우를 커버하였다.