𝝅번째 알파카의 개발 낙서장

screen

[프로그래머스 / JAVA] Level 2 124 나라의 숫자 (12899)

posts

알고리즘

시리즈 톺아보기

프로그래머스

프로그래머스
count

124 나라의 숫자 🔗

랭크 사용 언어
Level 2 JAVA

🔗 124 나라의 숫자

문제 설명 🔗

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

  • 124 나라에는 자연수만 존재합니다.
  • 124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다.

예를 들어서 124 나라에서 사용하는 숫자는 다음과 같이 변환됩니다.

10진법 124 나라 10진법 124 나라
1 1 6 14
2 2 7 21
3 4 8 22
4 11 9 24
5 12 10 41

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

제한사항 🔗

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

입출력 예 🔗

n result
1 1
2 2
3 4
4 11

풀이 🔗

124 나라라는 이상한 나라가 있다.

국제적으로 통용되는 10진법을 쓰지 않고, 굳이 124 법칙이라는 이상한 진법을 고수하여 당신을 피곤하게 만들고 있다.

이 124 진법을 해석하는 알고리즘을 구성하여 만성 피로에서 벗어나보자.


규칙 자체는 별거 없다. [ 1, 2, 4 ] 순으로 번갈아가며 숫자가 표기된다.

10진법 124 나라
1 1
2 2
3 4
4 11
5 12
6 14
7 21
8 22
9 24
10 41
11 42
12 44
13 111
14 112
15 114

대충 이런 식으로 전개된다. 끝에 3이 아닌 4가 껴버리는 바람에 살짝 헷갈릴 수 있다.

규칙적인 데이터을 가지고 있으므로, 이를 통해 패턴을 유추해보자.

숫자 3개로 표현되니, 3진법을 만드는 방식과 매우 유사할 것이다.


MOD 연산을 통해 124 진법으로 변환할 수 있다.

  1. n % 3 연산을 수행하여 나머지를 구한다.
  2. n / 3 연산을 수행하여 n에 할당한다.
    1. 만약 n % 3 == 0일 경우 할당된 n에서 1을 뺀다.
  3. n = 0일 때까지 위 과정을 반복한다.

n = 5일 경우, 아래와 같다.

  1. 5 % 3 연산을 수행하여 나머지 2를 구한다.
    1. 124의 두 번째 숫자는 2이므로, 첫 번째 자리는 2가 된다.
  2. 5 / 3 연산을 수행하여 n을 1로 할당한다.
  3. 1 % 3 연산을 수행하여 나머지 1을 구한다.
    1. 124의 첫 번째 숫자는 1이므로, 두 번째 자리는 1이 된다.
  4. 1 / 3 연산을 수행하여 n을 0으로 할당한다.
  5. n = 0이므로 종료한다. 5는 124 진법으로 12가 된다.

그러나 n % 3 == 0일 경우 특이한 조건이 붙는데, 이는 3의 배수를 직접 연산해보면 알 수 있다.

  1. 6 % 3 연산을 수행하여 나머지 0을 구한다.
    1. 124의 0 번째 숫자는 4이므로, 첫 번째 자리는 4가 된다.
  2. 6 / 3 연산을 수행하여 n을 2로 할당한다.
  3. 2 % 3 연산을 수행하여 나머지 2을 구한다.
    1. 124의 두 번째 숫자는 2이므로, 두 번째 자리는 2가 된다.
  4. 2 / 3 연산을 수행하여 n을 0으로 할당한다.
  5. n = 0이므로 종료한다. 6은 124 진법으로 24가 된다...?

계산에 의하면 24가 되는데, 실제로는 14다. 3의 배수일 경우, 자릿수가 하나 올라가기 때문에, n을 하나 빼서 이를 보정해줘야 한다.

코드 🔗

JAVA

0import java.util.ArrayList;
1import java.util.Collections;
2
3/**
4 * 124 나라의 숫자 클래스
5 *
6 * @author RWB
7 * @since 2021.12.27 Mon 00:36:19
8 */
9class Solution
10{
11 private static final String[] DIGIT = { "4", "1", "2" };
12
13 /**
14 * 해답 반환 메서드
15 *
16 * @param n: [int] 자연수
17 *
18 * @return [String] 해답
19 */
20 public String solution(int n)
21 {
22 ArrayList<String> list = new ArrayList<>();
23
24 while (n != 0)
25 {
26 int index = n % 3;
27
28 n /= 3;
29
30 // 인덱스가 0일 경우
31 if (index == 0)
32 {
33 n--;
34 }
35
36 list.add(DIGIT[index]);
37 }
38
39 Collections.reverse(list);
40
41 return list.stream().reduce(String::concat).isPresent() ? list.stream().reduce(String::concat).get() : "";
42 }
43}