[프로그래머스] 124 나라의 숫자

문제

---

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

프로그래머스

 

문제 분석

---

[제한사항]

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

1, 2, 4 만을 사용하는 나라에서 주어진 n 을 어떻게 나타내는 지 찾는 문제이다.

 

제한 조건이 크기 때문에 n*2 만 되도 시간 초과가 날 것이다.

 

문제 접근

---

우선 숫자 3개로 주어진 숫자로 만들어야 하기 때문에 주어진 숫자를 3으로 나누면 어떤 규칙이 보이지 않을까? 라고 생각하고 접근하였다.

 

그래서 10을 3으로 나누었다. ( 10 / 3 = 3 .. 1 )

그러고 보니 다음과 같은 규칙을 발견할 수 있었다. 

 

변경된 숫자 (41) = 2^(몫 - 1) 2^(나머지-1)

즉, 2의 2 승과 2의 0승의 조합으로 41 이 된다.

 

다른 예시로 20을 들어보자.

20 / 3 = 6 ... 2

처음으로 나온 나머지가 2로 첫 자리는 정해졌다. 2의 1승으로 2가된다.

 

6 / 3 = 2 .. 0 -> 1 ... 3 

다음으로 나오는 나머지 0 대신 3으로 만들고 대신 몫에서 1을 빼준다. 그럼 다음 자리는 2의 2승으로 4가 된다.

 

1 / 3 = 0 ... 1

마지막은 2의 0승으로 1이 된다.

 

합치면 142 가 된다.

 

위 규칙을 잘 활용해 코드를 작성하면 문제를 해결할 수 있다.

 

코드

---

import java.util.*;

class Solution {
    public String solution(int n) {
        String answer = "";

        StringBuilder sb = new StringBuilder();
    
        while(n > 0){
            int namuge = n % 3;
            n = n / 3;
            
            if(namuge == 0){
                namuge = 3;
                n--;
            }
            
            sb.insert(0, (int)Math.pow(2, namuge-1));
        }
        return sb.toString();
    }
}

 

주의

문제를 풀면서 문자열에 계속 + 하는 형식으로 결과를 내니 시간 초과가 난다.

String 에서는 + 연산을 하면 기존 객체에서 합쳐지는 것이 아닌 합쳐진 새로운 객체가 생성되는데 이 때문에 시간 초과가 난 것으로 예상된다.

 

따라서 문제를 풀기 위해 StringBuilder 를 사용하였다.