124 나라의 숫자

· 문제 설명

124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다.
124 나라에는 자연수만 존재합니다.
124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다.
자연수 n이 매개변수로 주어질 때, n을 124 나라에서 사용하는 숫자로 바꾼 값을 return 하도록 solution 함수를 완성해 주세요.

 

· 제한 사항

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

 

· 입출력 예

n	result
1	1
2	2
3	4
4	11
5	12
6	14
7	21
8	22
9	24

---

· Thinking 1

규칙 알아내기..!

1	1	몫 0
2	2
3	4	3의 배수 3까지 한자리 숫자 4
4	11	몫 1
5	12
6	14	3의 배수 6까지 두자리 숫자 14
7	21	몫 2
8	22
9	24	3의 배수 9까지 두자리 숫자 21
10	41	몫 3
11	42
12	44
13	111	몫 4
14	112
15	114
16	121	몫 5
17	122
18	124
19	141	몫 6
20	142
21	144
22	211	몫 7

 

---

· Thinking 2

1. n % 3 == 1 : 마지막 자리 1

2. n % 3 == 2 : 마지막 자리 2

3. n % 3 == 0 : 마지막 자리 4

 

1 → 1	4 → 11	7 → 21
2 → 2	5 → 12	8 → 22
3 → 4	6 → 14	9 → 24

 

이것도 몫을 또 나누었을때로 나뉨

 

3 → 0

4 → 1

5 → 2

6 → 0

---

· Thinking 2

- 몫 * 제수 + 나머지 = n

- 몫 = (n - 나머지) / 제수

 

만약 n이 10이라면,

10 % 3 == 1 -> 1

10  /  3 == 3 -> 4

해서 result 값 41

 

만약 n이 18이라면,

18 % 3 == 0 -> 4

18 / 3 == 6

6 % 3 == 0

 

n = (n-1) / 3 이 관건..!
내가 생각한 규칙으로는 123/456/789 이런 식으로 3의 배수를 기준으로 나뉘는데
3의 몫은 1이라서 그냥 나눠서 몫을 구하면 12/345/678/9 로 되기 때문에 X 
따라서 (n-1) / 3으로 해결.. 과연..!

---

· 완성 코드

class Solution {
  public String solution(int n) {
      String answer = "";
      while (n >= 1) {
          switch (n % 3) {
              case 0:
                  answer += "4";
                  break;
              case 1:
                  answer += "1";
                  break;
              case 2:
                  answer += "2";
                  break;
          }
          n = (n-1) / 3;
      }
      
      StringBuffer buffer = new StringBuffer();
      buffer.append(answer);
      return buffer.reverse().toString();
  }
}

 

---

· 다른 사람의 풀이

class Solution {
  public String solution(int n) {
      String[] num = {"4","1","2"};
      String answer = "";

      while(n > 0){
          answer = num[n % 3] + answer;
          n = (n - 1) / 3;
      }
      return answer;
  }
}

 

---

· 문제 출처

https://programmers.co.kr/learn/courses/30/lessons/12899

알고리즘 연습 - 124 나라의 숫자 | 프로그래머스