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

 

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

프로그래머스

 

 

이 문제는 LeetCode easy 문제에서 풀었던 것과 비슷하다.

처음에는 백트래킹으로 해서 쭉 올라가는 완전 탐색으로 할까 했는데

제한사항이 n ≤ 500,000,000 이하이길래 절대 안되겠구나..^^ 무조건 수학이겠군... 싶었다. 

 

보면 알 수 있지만 수가 반복된다. 1, 2, 4 이러면 아주.. 예전에 풀었던 요일 구하는 문제처럼 1, 2, 4 배열을 만들고 이를 인덱스로 접근해서 풀 수 있다! 그래서 이 배열의 사이즈를 나누면서 하면 값을 구할 수 있다. 그 후 꼭 reverse로 뒤집어줘야 한다. 맨 뒤에서부터 연산했으니.. (나눗셈)

 

i는 인덱스 위치, answer에 num[i]를 넣어준다. 그리고 n을 업데이트해주는데 여기서 1을 빼주지 않으면 정확한 값이 나오지 않는다.

살짝 아리까리하지만 직접 해보면 공식을 구할 수 있다. 

 

string solution(int n) {
    string answer = "";
    char num[3] = {'1', '2', '4'};
    
    while(n){
        int i = (n-1) % 3;
        answer += num[i];
        n = (n-1) / 3;
    }
    reverse(answer.begin(), answer.end());
    return answer;
}