[Lv2] 124 나라의 숫자

https://programmers.co.kr/learn/challenges

프로그래밍 강의 | 프로그래머스

문제 설명

 

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

---

입출력 예

n	result
1	1
2	2
3	4
4	11

---

개발자들에게 2진법, 16진법 같은 경우는 흔하게 접할 수 있으니 어렵지 않을겁니다.

 

혼란을 방지하기 위해 1,2,4 대신 A,B,C로 생각하겠습니다.

 

규칙을 찾기 어려울 땐 수를 넓게 봅시다.

 

n	result
1	A
2	B
3	C

n	result
4	AA
5	AB
6	AC
7	BA
8	BB
9	BC
10	CA
11	CB
12	CC

n	result
13	AAA
14	AAB
15	AAC
16	ABA
17	ABB
18	ABC
19	ACA
20	ACB
21	ACC
22	BAA
...
39	CCC
40	AAAA

3까지는 한자리, 3+3^2=12까진 두자리, 3+3^2+3^3=39까진 세자리네요.

 

int length = 1;
int cal = 0;
int precal = 0;
while(true) {
	cal += Math.pow(3, length);
	if(n<=cal) break;
	length++;
	precal = cal;
}

n이 3^i승의 합들보다 언제 작거나 같은지 확인합니다.

 

그리고 루프 직전에 그 전단계의 합도 precal에 기록해둡니다.

 

length는 몇 자리 수가 될지 기록합니다.

 

 

앞자리부터 적어나갈 것인데,

 

항상 덩어리(1~3 혹은 4~12 혹은 13~39 같은..)의

 

1/3까지가 A로 시작하고, 1/3~2/3는 B로 시작하고 나머지는 C로 시작합니다.

 

 

덩어리의 갯수(cal-precal)를 3개로 나눈 조각(slice)을 두고,

 

이 n이 precal로부터 1번재 조각 영역에 있는지, 2번째인지 3번째인지 봅시다.

 

각각 A/B/C가 될 것입니다.

 

가장 쉽게 생각할 수 있는 4~12를 보면,

 

4~6=3+3 / 7~9=3+6 / 10~12=3+9로 나뉩니다. precal(3)에 조각값(3,6,9)이 더해진 수가 영역의 마지막 값입니다.

 

그 외 / precal+slice 초과 / precal+slice*2 초과 로 ①②③순으로 검사해줍니다. 세 영역 중 어딘간 있으니까요.

  ③             ②                        ①

 

StringBuffer sb = new StringBuffer();
for(int i=1;i<=length;i++) {
	int slice = (cal-precal)/3;
	if(n>precal+slice*2) {
		sb.append("4");
		precal = precal+slice*2;
	} else if(n>precal+slice) {
		sb.append("2");
		cal = precal+slice*2;
		precal = precal+slice;
	} else {
		sb.append("1");
		cal = precal+slice;
	}
}
return sb.toString();

C(4) / B(2) / A(1)를 기록해주고,

 

다음 자릿수를 보기 위해 cal과 precal을 조정해야합니다.

 

2/3 초과 ~ 마지막에 속했다면, 마지막값(cal)은 그대로, 덩어리 이전값(precal)은 2/3값인 precal+slice*2.

 

1/3 초과 ~ 2/3 이하에 속했다면, 마지막값(cal)은 precal+slice*2, 이전값(precal)은 1/3값인 precal+slice.

 

처음 ~ 1/3 이하에 속했다면, 마지막값(cal)은 precal+slice, 이전값(precal)은 그대로.

 

자릿수(length)만큼 for문을 돌면서 앞부터 A/B/C(1/2/4)를 저장 후, 문자열로 출력하면 정답.