문제
https://programmers.co.kr/learn/courses/30/lessons/12899
풀이
나사 빠진 진법 문제. 나머지 연산을 조금 꼬아서 풀어야 한다.
mod 3 연산과 같다. 다만 0이 없다.
mod 3 연산과 동일하게 만든다.
1,2는 나머지 연산과 같고, 몫이 1인 경우는 몫에 1을 뺀다.
1 -> 0... 1
2 -> 0... 2
3 -> 1... 0 -> -1 -> 0... 0
나머지가 0인 경우는 3으로 생각하면 되고, 124 나라 표기 방법대로 3을 4로 생각하면 된다.
즉, 나머지 0인 경우는 4가 된다.
0이 4가 되도록 매핑은 배열을 이용해서 구현했다.
알고리즘 순서를 자세히 설명하면
1. 숫자를 3으로 나눠서 몫과 나머지를 구한다.
2. 몫이 0이면 중단한다.
3. 나머지를 저장한다.
4. 나머지가 0이면 몫에서 1을 뺀다.
5. 몫을 숫자로 해서 1번부터 다시 시작한다.
6. 중단된 경우, 저장한 나머지를 모으면 정답
위 규칙을 적용하면 아래와 같이 정답이 나온다.
n=1인 경우
5/3 = 1... 2
1/3 = 0... 1
정답은 12
n=11인 경우
11/3 = 3... 2
3/3 = 1... 0 -> (-1) -> 0.. 0
32 -> 3은 4로 매핑
정답은 42
n=12인 경우
12/3 = 4... 0 -> (-1) -> 3... 0
3/3 = 1... 0 -> (-1) -> 0... 0
33 -> 3은 4로 매핑
정답은 44
+ 웬만하면 stringBuffer/Builder를 이용해서 immutable string을 생성하지 않도록 하자
소스코드
class Solution {
public String solution(int n) {
StringBuffer sb = new StringBuffer();
int[] numberMap = {4, 1, 2};
while(n > 0) {
sb.append(numberMap[n%3]);
n = n/3 - ((n%3 == 0) ? 1:0);
}
sb.reverse();
return sb.toString();
}
}