124 나라의 숫자

문제 링크 => 코딩테스트 연습 - 124 나라의 숫자 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 124 나라의 숫자

---

구현 문제이다.

 

124 나라에서는 숫자 1, 2, 3, 4, ... 를 다음과 같이 표기한다.

 

1 => 1   /   2 => 2   /   3 => 4

4 => 11   /   5 => 12   /   6 => 14

7 => 21   /   8 => 22   /   9 => 24

10 => 41   /   11 => 42   /   12 => 44

...

 

124 나라의 숫자를 분석해보면 다음과 같은 규칙성을 가지고 있다.

 

예를 들어서 12421 를 살펴보도록 한다.

 

12421 = 1 * 3^4 + 2 * 3^3 + 3 * 3^2 + 2 * 3 + 1

 

여기서 1, 3, 3^2, ... , 3^(m-1), ... 이런식으로 계수에 곱해지면서 더하는 형태인데 계수가 1, 2 일때 그대로 곱하고 4 일때 3을 곱한다.

 

그렇다면 124 나라의 숫자를 구하는 방법은 다음과 같은 규칙을 가지고 어떻게 구할까?

 

먼저 변수 sum, x 를 설정하고 sum = 1 + 3 + 3^2 + ... + 3^m , x = 3^m 를 만족하는 m 이 있다고 한다.

 

sum <= n  && n < (sum + 3^m * 3)  두 조건을 동시에 만족하는 m 을 발견할 경우 n 값이 0 이 될 때까지  다음과 같은 반복문을 돌린다.

 

그 전에 다음과 같은 예시를 살펴보도록 한다.

 

142 를 예로 들면, 142 = 3^2 + 3 * 3 + 2 = 20 이다.

 

여기서 sum = 13, x = 9 인데 (20 - 13) >= (1 - 1) * x && (20 - 13) < 1 * x 를 만족하는 것을 확인할 수 있다.

 

일반화 하자면 tmp = n - sum 이라고 할 때 tmp >= (i - 1) * x && tmp < i * x  ( i = 1, 2, 3 ) 인 경우 i 에 대하여 124 숫자를 구할 수 있음을 알 수 있다.

 

이러한 규칙성을 가지고 코드를 작성하면 다음과 같다.

 

풀이 Code

 

#include <string>
#include <vector>

using namespace std;

string solution(int n) {
	string answer = "";
	int sum = 0, x = 0;
	for (int i = 1; i <= 500000000; i *= 3) {
		sum += i;
		if (sum <= n && n < (sum + i * 3)) {
			x = i;
			break;
		}
	}
	
	while (n) {
		int op = 0;
		for (int i = 1; i <= 3; i++) {
			int tmp = n - sum;
			if (tmp >= (i - 1) * x && tmp < i * x) {
				op = i;
				break;
			}
		}

		if (op == 1) answer += "1";
		else if (op == 2) answer += "2";
		else answer += "4";

		sum -= x;
		n -= x * op;
		x /= 3;
	}

	return answer;
}