[ 프로그래머스-lv2 / 진법변환 ] 124 나라의 숫자

1. 문제

---

 

프로그래머스

• 124 나라의 숫자

• darklight

  sublimevimemacs

  C++ 

문제 설명

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이하의 자연수 입니다.

 

 

2. 소스코드

---

1회차

 

- 진법 개념으로 접근하지 않음.

- 3 + 3^2 + 3^3 ..... 구간별로 규칙을 파악하고 접근.

- 정답은 구했지만, 효율성 테스트에서 NP가 떴다.

 3^19이 11억이고, 입력n은 5억 이하. base와 cntNum(자리수)를 구하는데는 최대 19번이 필요하고

 자리수별로 1,2,4를 구별하는데는 nlog3이므로 충분히 가능할 줄 알았는데, pow연산 19번이 너무 컸나보다.

 

라고 생각했는데, 직접 3^0부터 3^19까지 배열에 일일이 넣고 돌려본 결과, 별 차이 없었다.

int num[] = { 1,3,9,27,81,243,729,2187,
        6561,19683,59049,177147,531441,1594323,4782969,
        14348907,43046721,129140163,387420489,1162261467 };

그래서 pow 연산 그 자체가 문제는 아닌가보다.

라고 생각했는데, base를 구할때도 pow를 사용하지 않게 바꾸니 효율성이 ALL PASS됬다.

 

 

//int base = pow(3, cntnum);
int base = num[cntnum];

- pow 자체가 그리 느리진 않다. 일반적인 범위내에선 pow 함수는 상수시간내에 해결된다.

 

- 실제로 이렇게 풀면 절대 좋은 소리 못들을 것...

#include <string>
#include <vector>
#include <math.h>
#include <iostream>

using namespace std;

string solution(int n) {

    int num[] = { 1,3,9,27,81,243,729,2187,
         6561,19683,59049,177147,531441,1594323,4782969,
         14348907,43046721,129140163,387420489,1162261467 };

    string answer = "";
    int sum = 0, cntnum = 0;
    int i = 1;

    while (true) {
        if (sum + num[i] < n) {
            sum += num[i];
        }
        else {
            cntnum = i;
            break;
        }
        i++;
    }
    /*
    while(true){
        int temp = pow(3, i);
        if(sum + temp < n ) {
            sum += temp;
        }
        else {
            cntnum = i;
            break;
        }
        i++;
    }
    
    int base = pow(3,cntnum);
    */
    int base = num[cntnum];
    int order = n - sum;

    while (cntnum != 0)
    {
        if (order <= base / 3) answer += "1";
        else if (base / 3 < order and order <= base / 3 * 2)
        {
            answer += "2";
            order -= base / 3;
        }

        else {
            answer += "4";
            order -= base / 3 * 2;
        }
        base /= 3;
        cntnum--;
    }
    cout << answer;

    return answer;
}

 

2회차

 

- 진법 개념으로 접근 시도.

- 3진법과의 차이는

 1) 3진법에서 0일때 124숫자는 4가 온다는 점.

 2) 4가 오면서 앞자리 전체에서 -1 이 발생한다는 점.

ex) 

숫자 10

3진법 : 100

124숫자 : 24

 

3진법에서 끝자리 0을 4로교체 : 104

교체한 자리수, 앞 전체에서 - 1 : [10(3진수) - 1(10진수)]4  = [02(3진수)]4 = 24

 

- 리터럴에서 index를 이용, 원하는 요소를 꺼내 쓸수 있다.

"01234"[1] = '1'

"abcde"[2] = 'c ' 

 

#include <string>
#include <vector>

using namespace std;

string solution(int n) {
	string ans;
	int remain = 0;
	while (n)
	{
		remain = n % 3;
		n /= 3;
		if (remain == 0) n--;
		ans = to_string(remain) + ans;
	}
	return ans;
}