23.04.15. programmers 코딩테스트 문제 풀기[2]

슬슬 어려워 지는 것 같아서 실시간 문제풀기 기록을 가감없이 남겨보려고 한다.

 

문제: 3진법 뒤집기

 

[문제 설명]
자연수 n이 매개변수로 주어집니다.
n을 3진법 상에서 앞뒤로 뒤집은 후, 이를 다시 10진법으로 표현한 수를 return 하도록 solution 함수를 완성해주세요.

[제한사항]
n은 1 이상 100,000,000 이하인 자연수입니다.

일단 자연수 n이 매개변수로 주어지는 함수인데,

3진법에서 앞뒤로 뒤집은 후 이를 10진법으로 표현한 수를 return하는 것이니까,

3진법으로 만들어야 한다. 

3진법으로 만드는 방법은 분명 함수가 있을 텐데, 아니면 3진법을 함수로 구현해도 될듯.

3진법은 0,1,2, 10, 11, 12, 20로 올라가니까,

3으로 얼마나 나눠지는지를 계산하면 될 것 같다.

그러니까 18은 3의 2승이 2개니까, 200일 듯. 표로 확인해보자

10:	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
3:	0	1	2	10	11	12	20	21	22	100	101	102	110	111	112	120	121	122	200

그러니까 이걸 구현하려면 주어진 자연수 n보다 작은 것 중에 가장 큰 3의 배수로 나누고, 나머지를 그보다 작은 3의 배수로 나누고 하는걸 반복해서 나머지까지 구하는 recursive한 함수로 만들 수 있을 것 같기도 하고,

 

아니면 3으로만 계속 나눠서 몇번 나눠지는지를 구하고, 그 몇번이라는 정보로 구현할 수도 있을 것 같다.

되나? 생각해보자.

 

n = 524일 때,

524 ÷ 3 = 2 + 3 × 174,

174 ÷ 3 = 3 × 58,

58 ÷ 3 = 1 + 3 × 19,

19 ÷ 3 = 1 + 3 × 6,

6 ÷ 3 = 3 × 2

 

맞나? 

 

다시 연결된 식으로 보면, (2 + 3 × ( 3 × (1 + 3 × (1 + 3 × (3 × 2) ) ) ) )

그럼 1이나 2가 남는 것에 앞의 3의 배수가 곱해지기 때문에, 

2 × 3^5 + 0 × 3^4 + 1 × 3^3 + 1 × 3^2 + 0 × 3^1 + 2 × 3^0 이 되고,

즉 삼진법으로는 201102가 된다.

 

그럼 이걸 함수로 어떻게 구현하지...

 

일단 recursive하게 해야 할 것 같다. 왜? recursive연습하려고.

근데 while로 구현하는게 더 간단할 것 같다.

recursive는 가독성이 안좋은건지 내가 익숙하지 않은건지를 모르겠다.

일단 둘 다 만들어 보자.

 

우선 while로 만든다고 하면,

자리수마다 세개의 값을 저장해야한다.

가장 처음에 3으로 나눴을 때의 몫과 나머지, 그리고 자리수

자리수는 얼마나 나눠질지 모르기 때문에, 오름차순으로 정리하고, length - x 로 계산해야 하지 싶다. 그럴필요가 없나? 어차피 뒤에서부터 하나씩 빼 쓰면될것같으니까.... list로 나머지만 저장하면 되는구나. 

위의 n=524로 생각해보면, 나머지를 순서대로 쓰면, 2,0,1,1,0과 몫 2. 하필 대칭이라서 헛갈린다.

 

다시, n = 326으로 해보자.

326

= (3 × 108 + 2)

= (3 × (3 × 36) + 2)

= (3 × (3 × (3 × 12) ) + 2)

= (3 × (3 × (3 × (3 × 4) ) ) + 2)

= (3 × (3 × (3 × (3 × (3 × 1 + 1) ) ) ) + 2)

= 1 × 3^5 + 1 × 3^4 + 0 × 3^3 + 0 × 3^ 2 + 0 × 3^1 + 2 × 3^0

= 110002 (3진) 

 

맞다. 그러니까 나머지값만 잘 보관하면 된다.

다시 정리하면 3으로 나누며 나머지 값을 저장하지만 몫이 3보다 작거나 같을 경우에는 몫을 저장한다는 규칙을 찾았다.

 

while문으로 구현하려면,

나머지가 몫과 같아질 때 while을 빠져나가도록 하면된다.

근데 이 때, 값을 저장해야 한, while을 true로 돌리고, if문으로 break하는게 맞겠다.

코드 작성하면서 생각해보니 몫이 3보다 작거나 같으면 나머지랑 몫이 같다 어차피. 

 

let n = 326
let vals = []
while (true) {
    vals.unshift(n%3)
    if (n < 3) {break}
    n = parseInt(n/3)
}
console.log(vals) // [1,1,0,0,0,2]

이제 주어진 문제에서 뒤집어야 하니,

 

array를 reverse 메서드로 돌리고나서 10진법으로 바꿔주면 된다. 

 

위에서 [1,1,0,0,0,2] 를 얻었으니, reverse하면 [2,0,0,0,1,1]

 

let n = 326
let vals = []
while (true) {
    vals.unshift(n%3)
    if (n < 3) {break}
    n = parseInt(n/3)
}
vals = vals.reverse()
console.log(vals) // [2,0,0,0,1,1]

잘 나온다. 

 

근데 생각해보니 어차피 reverse할거면 unshift가 아니라 push하면 되는거 아닌가?

let n = 326
let vals = []
while (true) {
    vals.push(n%3)
    if (n < 3) {break}
    n = parseInt(n/3)
}
console.log(vals) // [2,0,0,0,1,1]

맞다. 

 

이제 10진법 수로 바꿔보자. 바꿔보는 코드는 3진법 만드는 것의 역순이라고 생각하고 코드를 만들다보니,

3의 자리수 만큼의 곱하기를 해야하고 마침 index도 0부터 시작하니까, pop을 쓰려면 원래 순서로 쓰는게 좋겠다 싶었다.

3진법을 만들면서 바로 역순 10진법을 만들 수 있겠다는 생각도 들었다. loop는 한번에 끝낼 수 있으니 더 깔끔할 듯.

다만 array를 아예 안쓰려면 counter를 만들어야 하겠네.

 

라고 생각을 이어가면서 코드를 짜려고 보니, counter로 할 수 없었다. array는 unshift로 나머지값을 뒤로 밀면서 저장하는데, 계산이 끝났을 때 총 자리수가 나오니까, 10진법으로 다시 바꾸려면 원래 순서대로인 array를 가지는게 맞겠다.

 

그렇게 하니,

let n = 326
let vals = []
while (true) {
    vals.unshift(n%3)
    if (n < 3) {break}
    n = parseInt(n/3)
}
let res = 0
console.log(vals) // [1,1,0,0,0,2]

for (i in vals) {
    res += (3 ** i) * vals[i]
}
console.log(res) // 490 = 200011(3진법)

결과가 잘 나온다. 이걸 이제 정답 형식으로 함수에 담으면 된다.

function solution(n) {
    let vals = []
    while (true) {
        vals.unshift(n%3)
        if (n < 3) {break}
        n = parseInt(n/3)
    }
    let res = 0
    for (i in vals) {
        res += (3 ** i) * vals[i]
    }
    return res
}

테스트 코드는 잘 통과한다.

 

toString과 parseInt를 쓰면 간단하게 구현할 수 있어서 위와 같이 할 필요는 없다.

let n = 326
console.log(parseInt(n.toString(3).split('').reverse().join(''),3)) // 490

한번 머리를 굴려봤다. 아.. 재귀함수 안했다. 다음 기회에.