본문 바로가기

코딩테스트

[프로그래머스] 3진법 뒤집기 - js

문제설명 : 

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

 

첫번째 시도 :

function solution(n) {
    var answer = 0;
    let arr = []
    
    while(n > 0){
        arr.push(n%3)
        n = parseInt(n/3)
    }
    
    answer = arr.reverse().reduce((acc, cur, idx) => {
        if(idx == 0) return acc + cur
        else return acc + cur*(idx**3)
    },0)
    
    return answer
}

solution(45)

첫번째 시도에서는 거듭제곱의 순서를 잘못 사용해서 틀리고 있었다. 

거듭제곱 연산자(**)는 왼쪽 피연산자를 밑, 오른쪽 피연산자를 지수로 한 값을 구합니다 [MDN]

제대로 읽지도 않고 그냥 사용하려다 저질러버린 부끄러운 실수다..!

 

 

두번째 시도 : 

function solution(n) {
    var answer = 0;
    let arr = []
    
    while(n > 0){
        arr.push(n%3)
        n = parseInt(n/3)
    }
    
    answer = arr.reverse().reduce((acc, cur, idx) => {
        if(idx == 0) return acc + cur
        else return acc + cur*(3**idx)
    },0)
    
    return answer
}

solution(45)

여기서 정답이 나왔다. 

 

 

나의 풀이 : 

문제는 생각보다 간단했다. 2가지가 핵심이었던 것 같다. 

1) 3진법을 어떻게 코드로 구현할 것인가.

2) 3진법으로 구현된 코드를 어떻게 다시 10진법으로 돌릴 것인가? 

 

 

1) 3진법을 어떻게 코드로 구현할 것인가 : 

이것을 고민하기전에 3진법을 한번 그려보았다. 

3으로 나누기

3으로 나누어진 저 몫과 나머지를 순서대로 나열하면 1200이 된다. 이것이 45를 3진법으로 표기한 것이다. 

이것을 어떻게 코드로 구현할까? 

 

 

    while(n > 0){
        arr.push(n%3)
        n = parseInt(n/3)
    }

while문을 활용한다. while문이 종료되는 조건은 n이 0 될 때이다. (밑에서 계속 설명하겠다.) => while( n > 0 ) 

나머지를 구한다 => n % 3 

그리고 이 나머지 값을 arr에 넣는다. => arr.push(n%3) 

그 다음 주어진 수에 나눈 몫을 다시 넣어준다. 넣어줄 때 parseInt를 해준다. => n = parseInt(n/3)

parseInt를 하여 1/3과 같이 더 이상 나누어도 몫이 나올 수 없을 때, 

n을 0으로 만들어주어 while을 종료시킨다. 

 

이렇게 하면 arr에 우리가 구하고자 하는 45의 3진수가 담긴다. [0,0,2,1]

 

 

 

2) 3진법으로 구현된 코드를 어떻게 다시 10진법으로 돌릴 것인가? :

 

이것은 그냥 수학공식을 그대로 활용하면 된다. 

3진수를 10진수로

이것을 코드로 구현하면 다음과 같다. 

    answer = arr.reduce((acc, cur, idx) => {
        if(idx == 0) return acc + cur*1 // 첫번째는 x 1 이므로 그냥 곱한다.
        else return acc + cur*(3**idx) // 두번째부터 각 자리의 수에 3의 제곱을 곱한다.
    },0)

 

 

그런데, 문제가 요구한 것은 뒤집은 수를 더하는 것이었다. 그러면 배열을 reverse() 해주면 된다. 

    answer = arr.reverse().reduce((acc, cur, idx) => {
        if(idx == 0) return acc + cur
        else return acc + cur*(3**idx)
    },0)

 

 

약간의 리팩토링 : 

사실 여기서 reverse를 사용하면 O(n^2) 되어버리기 때문에 비효율적이다. 

그렇다면 배열에 넣어줄 때부터 거꾸로 넣어주는 방법이 있다. 

unshift를 사용하는 것이다. 

function solution(n) {
    var answer = 0;
    let arr = []
    
    while(n > 0){
        arr.unshift(n%3)
        n = parseInt(n/3)
    }
    
    answer = arr.reduce((acc, cur, idx) => {
        if(idx == 0) return acc + cur
        else return acc + cur*(3**idx)
    },0)
    
    return answer
}

solution(45)

 


사실 진법을 바꾸는 방법은 내장함수를 통해서도 구현이 가능하다고 한다. (https://medium.com/web-dev-note/javascript-%EC%A7%84%EB%B2%95-%EB%B3%80%ED%99%98-330694083495)

그런데, 직접 머리를 써가며 구현을 해보고 싶었다.