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

문제설명

124나라 라는 의미는 10진수가 아닌 1,2,4 로 값을 표현하라는 뜻이다

즉, 수가 입력되면 위의 예시처럼 124 표기법으로 결과 값을 출력하면된다

알고리즘

1. 구하고자 하는 값을 입력 받는다

2. 3으로 나눴을 때 나머지가 0인경우는 4를 저장하고, 그렇지 않은 경우 그 나머지를 저장한다

3. 나머지가 0인 경우에는 몫을 1 빼고 반복하여 연산을 진행한다

4. 몫과 나머지 모두 0 이되는 경우 연산을 중지하고, 저장된 값을 뒤집어서 반환한다

코드

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

string solution(int n) {
    string answer = "";
    
    while(1){
        if(n%3==0 && n/3==0)
            break;
        if(n%3==0){//나머지가 0인 경우 
            answer+='4';//4를 붙임 
            n=(n/3)-1;//몫 -1 
        }
        else{//나머지가 0이 아닌 경우 그 나머지 값을 그대로 붙이기 
            int mod = n%3;
            answer+=to_string(mod);
            n=n/3;
        }
    }
    reverse(answer.begin(),answer.end()); //거꾸로 값이 삽입되기 때문에 뒤집기 
    return answer;
}

고찰

우리가 2진법을 사용할 때 쓰는 연산은 2로 계속 나눠서 그 몫과 나머지를 체크한다

따라서 이 문제는 3진수 인것처럼 계산하는 것이 우선 첫번째 아이디어이다

 

위의 방법은 124방식이 아닌 012방식인데, 따라서 나머지가 0이 나온 경우에는 4로 생각한다 

하지만 그게 끝이 아니라 몫에서 1을 뺀뒤 연산을 진행해야 한다 

 

사실 위의 아이디어까지는 순조롭게 되었지만, 1을 뺀다는 점을 명확하게는 이해 못했다 구글링을 통해서 이해했는데, 참고한 블로그는 다음과 같다

 

https://yabmoons.tistory.com/692