[프로그래머스] level 2 - 124 나라의 숫자 (C++)

머리 아픈 날에 풀려고 잡았다가 외않되??? 했던 문제... 역시 멀쩡한 컨디션에 잡으니까 금방 풀린다.

그리고 난 천재가 아니라서 글과 그림으로 생각을 정리해야 문제가 풀린다. 다음부턴 노트북만 붙잡고있지 말자...

 

문제풀이

124 나라는 자연수만 존재하고, 모든 숫자를 1, 2, 4 로 나타낸다.

여기서 3진법과 다른 점은 숫자 0을 표현하지 않는다는 건데, 그 때문에 3진법과 똑같이 하려고 하면 1씩 밀려 골치가 아프다.

물론 처음부터 n에 1을 빼서 하는 방법도 있지만, 나는 다른 방식으로 접근했기 때문에 그 방법은 패스하도록 하겠다.

 

참고로 124로 설명하면 헷갈리므로 123으로 바꾸어 설명할테니 잘 알아듣길 바란다.

먼저, 123으로 나타내는 수의 규칙을 보면 해당 자릿수가 나타내는 값은 3의 n승인 것을 알 수 있다.

 

ex) 6(10) = 13(123) = 3^1 * 1 + 3^0 * 3 = 6

ex) 10(10) = 31(123) = 3^1 * 3 + 3^0 * 1 = 10

 

이 점에서 착안하여 식을 세워보면 이렇다.

 

N = 3^n * Kn + ... + 3^1 * K1 + 3^0 * K0   ( Kn = 1,2,3 )

이를 3으로 묶어 나타내면 K0 + 3(K1 + 3(K2 + ... + 3(Kn-1 + 3(Kn))...)) 형식으로 나타낼 수 있다.

 

따라서 나는 N을 0이 될때까지 3으로 나누면서 파생되는 나머지를 Kn 으로 사용했다.

그런데 여기서 3진법과 달리 123수는 3으로 나누어 떨어지는 숫자까지 표현한 다음 자릿수가 올라가므로,

나머지가 0일때 몫에 1을 빼주는 식으로 예외처리를 해주었다.

 

#include <string>
#include <vector>
using namespace std;

string solution(int n) {
    string answer = "";
    string reverse = "";
    int remain;
    
    while(n>0) {
        remain = n % 3;
        if (remain==0) { // 나누어 떨어지면
            n = n / 3 - 1; // 몫에서 1 제외
            reverse += "4";
        }
        else { // 나누어 떨어지지 않으면 그대로
            n = n / 3;
            reverse += to_string(remain);
        }
    } 
    for (int i = reverse.size() - 1; i >= 0; i--){
        answer += reverse[i];
    }
    return answer;
}

포스팅하면서 다시 생각해보니, reverse에 넣고 마지막에 바꾸는 것보다 answer = remain + answer 이 훨씬 깔끔할 것 같다. 이걸 왜 생각 못했지? 역시 머리가 잘 안돌아갈때 문제를 풀면 코드가 참 별로다...

 

+다른사람의 풀이를 보니 나머지가 1,2일때와 0일때를 조건문으로 나누지 않고 그냥 "412"[remain] 이렇게 하더라. 난 인덱스를 저런 식으로 활용할 수 있는줄은 처음 알았다...