티스토리 뷰
https://programmers.co.kr/learn/courses/30/lessons/12899
코딩테스트 연습 - 124 나라의 숫자
programmers.co.kr
문제 설명
124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다.
- 124 나라에는 자연수만 존재합니다.
- 124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다.
예를 들어서 124 나라에서 사용하는 숫자는 다음과 같이 변환됩니다.
![](https://blog.kakaocdn.net/dn/BltW5/btruezeUFtt/bFcIXi4gC55isFUT3EhEfK/img.png)
자연수 n이 매개변수로 주어질 때, n을 124 나라에서 사용하는 숫자로 바꾼 값을 return 하도록 solution 함수를 완성해 주세요.
문제 풀이
3진수가 증가하는 것과 비슷한 과정으로 증가한다. 10진수에 해당하는 124진수와 몇 가지 수에서 3으로 나눈 몫과 나머지를 아래에 나열했다. nums = ['4', '1', '2'] 로 설정한다.
1: 1
2: 2
3: 4 -> 1 0
4: 11 -> 1 1
5: 12
6: 14 -> 2 0
7: 21
8: 22
9: 24 -> 3 0
10: 41
11: 42
12: 44 -> 4 0
13: 111 -> 4 1
14: 112 -> 4 2
n이 최대 5억이므로 순차적으로 탐색하는 과정으로는 절대 해결할 수 없고 반드시 규칙(패턴)을 찾아야한다.
진수문제는 보통 n진수로 나는 목과 나머지를 활용하여 문제를 해결할 수 있다.
1, 2, 3 을 먼저 보면 3으로 나눠서 몫은 0 나머지는 각각 1, 2, 0 인데 나머지 1, 2, 0에 124진수 1, 2, 4가 대응된다는 것을 알 수 있다.
이제 몫이 1보다 큰 수 5를 보면, 5를 3으로 나눴을 때 몫은 1 나머지는 2이다. 몫이 0보다 큰 경우는 다시 그 몫을 3으로 나눠 몫과 나머지를 구한다. 1을 3으로 나누면 몫은 0 나머지는 1이다. 따라서 5는 나머지로 2, 1 가지므로 1-> 1 2 -> 2 즉 124진수로 12가 되어야 한다.
여기서 주목해야 할 점은 3의 배수인 숫자들이다. 3의 배수인 숫자 6를 예를 들어보자. 6은 3으로 나눴을 때 몫이 2 나머지가 0이다. 3의 배수인 수들을 나열해 보면 3으로 나눈 몫이 0보다 클 때, 몫에 1을 빼서 다시 3으로 나눈 과정을 반복해야한다는 점을 알 수 있다. 6 -> (2, 0) -> 1%3 = 1, 따라서 6은 나머지로 0과 1를 차례로 가진다.
그러므로 6은 124진수로 14임을 알 수 있다.
요약하면
1. n이 3의 배수인 경우
2. n이 3의 배수가 아닌 경우
2가지 경우로 나눠서 해결할 수 있다.
def solution(n):
nums = ['4', '1', '2']
s = ''
answer = 0
while True:
q = n // 3
r = n % 3
if r == 0:
q = q - 1
s = s + nums[r]
n = q
if q == 0:
break
answer = s[::-1]
return answer
'알고리즘' 카테고리의 다른 글
카운팅 정렬 알고리즘(Counting Sort) / 계수 정렬 (0) | 2022.03.11 |
---|---|
[프로그래머스] 다단계 칫솔 판매 - 파이썬 (0) | 2022.03.08 |
[프로그래머스] 기능개발 - 파이썬 (0) | 2022.02.24 |
[프로그래머스] 프렌즈 4블록 - 파이썬 (0) | 2022.02.20 |
[프로그래머스] 점프와 순간 이동 - 파이썬 (0) | 2022.02.17 |
- Total
- Today
- Yesterday
- 피움 6주차 회고
- ZNS
- 스프링 프레임워크
- 네트워크
- 팀프로젝트
- 2차 데모데이
- 알림기능개선기
- dm-zoned
- 런칭 페스티벌
- Spring
- 3차 데모데이
- 8주차 회고
- CI/CD
- 스프링 부트
- 우테코 회고
- ZNS SSD
- 스프링 Logback
- 알림개선기
- 우테코
- 회고
- 백준
- 5주차 회고
- dm-zoned 코드분석
- 환경 별 로깅 전략 분리
- 프로젝트
- jpa
- 파이썬
- java
- 피움
- 스프링MVC
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | ||||
4 | 5 | 6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 | 24 |
25 | 26 | 27 | 28 | 29 | 30 | 31 |