[ 프로그래머스 Level 2 124 나라의 숫자 ] 문제 풀이(Java)

개인적으로 재미있는 문제였습니다!

 

접근 방식 잘 못하면 시간 초과가 날 수 있기 때문에 효율성까지 생각해야하는 문제입니다.

 

 

문제 보기

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

프로그래머스

 

문제 설명

 

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

1. 124 나라에는 자연수만 존재합니다.
2. 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

 

나의 풀이

 

처음 생각한 방식)

 

처음에는 1, 2, 4를 가지고 표현할 수 있는 모든 수를 찾아야하는 완전탐색 문제인가 생각했습니다. 재귀 방식으로 n번째 수까지 모두 구해야하나 하고 n의 범위를 봤더니 500,000,000,,, 택도 없는 방법입니다.

 

다른 분들의 블로그 글을 보고 힌트를 얻었습니다.

(나도 누군가에게 도움을 줄 수 있는 블로그 작성자가 되고 싶다!)

 

1, 2, 4 세 가지의 수로 수를 나타내야하므로 3진법으로 나타내주면 됩니다.

 

다만 3진법 같은 경우에는 0, 1, 2 숫자로 나타내기 때문에 

아! 0이 나올 자리에는 대신해서 4를 넣어주면 되겠구나!라고 생각했는데 예외가 발생했습니다.

예외)

n이 3인 경우에

 

정답                     4

내 코드 결과값      14

단순히 0을 4로만 바꿔주면 되는 것이 아니었습니다.

 

간과한 점이 0은 자리수를 바꿔주기 위해 존재하는 숫자이기 때문에 n%3이 0일 때는 재귀를 호출할 때 1을 빼줘야 합니다.

 

 

코드

class Solution {
  static StringBuilder sb = new StringBuilder(); 
  
  static void ternary(int n){
      if(n == 0) return;
      if(n%3 == 0)
          ternary(n/3-1);
      else
          ternary(n/3);
      if(n%3 == 0)
          sb.append(4);
      else
          sb.append(n%3);
  }
  public String solution(int n) {
      String answer = "";
      ternary(n);
      answer = sb.toString();
      return answer;
  }
}

 

결과

정확성과 효율성 모두 통과입니다!