[2025.01.10] 3진법 뒤집기

문제 설명

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

 

 

제한사항

• n은 1 이상 1000,000,000 이하인 자연수입니다.

 

 

입출력 예

n			result	설명
45			7	답을 도출하는 과정은 다음과 같습니다. n(10진법)=45, n(3진법)=1200, 앞뒤 반전(3진법)=0021, 10진법으로 표현=7 따라서 7을 return 해야 합니다.
125			229	답을 도출하는 과정은 다음과 같습니다. n(10진법)=125, n(3진법)=11122, 앞뒤 반전(3진법)=22111, 10진법으로 표현=229 따라서 229을 return 해야 합니다.

 

 

문제 풀이

풀이 언어 : C++

#include <string>
#include <vector>
#include <cmath>
using namespace std;

int solution(int n) {
    int answer = 0;
    vector<int> reverse_trinary_digit;
    
    // 앞뒤 반전 3진수 구하기
    while(n>2)
    {
        reverse_trinary_digit.push_back(n%3);
        n/=3;
    }
    reverse_trinary_digit.push_back(n);
    
    // 3진수 -> 10진수로 변환하기
    for(int i=0; i<reverse_trinary_digit.size(); i++)
    {
        answer+=reverse_trinary_digit[reverse_trinary_digit.size()-i-1]*pow(3, i);
    }
        
    return answer;
}

문제에서 말한 풀이방법 대로 풀어보자. 일단 3진법으로 변환한 후 그걸 뒤집고 10진법으로 표현하는 순서로 진행하면 될 것 같다.

 

먼저 3진법으로 변환하자. n이 0 또는 1 또는 2가 될 때까지 계속 나누면서 나머지를 저장하고 마지막에는 n을 저장하면 3진법을 구할 수 있다. 근데 이렇게 저장하게 되면 자동으로 앞뒤가 반전되어 저장되기 때문에 이대로 진행하면 될 것 같다. 3으로 나눈 나머지를 reverse_trinary_digit 벡터에 저장하고 n은 3으로 나눈 몫으로 업데이트 한다. 반복문을 빠져나와서 n을 reverse_trinary_digit에 저장한다.

 

이미 뒤집어진 3진법의 수를 가지고 이제 10진법으로 표현하기만 하면 된다. 10진법으로 표현하기 위해 3진법의 뒤에서 부터 3의 n제곱을 곱해주면 된다. n은 0부터 reverse_trinary_digit-1까지다. 입출력 예 1로 예시를 들자면 1*3의 0제곱+2*3의 1제곱... 이렇게 나아가는 것이다. 이렇게 더한 수를 answer에 차곡차곡 더하면 answer이 완성된다.

 

참고 사항

3진법으로 표현하는 방법, 3진법으로 10진법으로 바꾸는 방법이 잘 기억이 안나 찾아보면서 풀었다.

 

10진법으로 N진법으로 변환하기 위해서는 10진법의 수를 N으로 계속 나누면서 나머지를 보면 된다. 그리고 마지막에 몫이 0~N-1의 수가 나오면 계산을 중단하고 방금 나온 몫부터 여직 나온 나머지를 모두 나열하면 된다. 내가 위에서 사용한 계산은 나머지가 나올 때마다 벡터에 넣은 것이므로 이를 반대로 나열한게 된 것이다.

N진법을 10진법으로 바꾸기 위해서는 10진법이 어떻게 구성되어 있는 것인지 고민해보면 된다. 10진법은 일의 자리가 10의 0제곱을 곱해 더한 것이고 십의 자리가 10의 1제곱을 곱해 더한 것이다. 백의 자리는 10의 2제곱을 곱해 더한 것이다. 그렇기 때문의 N진법도 마찬가지다. 3진법의 맨 뒷자리는 3의 0제곱, 3진법의 그 다음 앞자리는 3의 1제곱이다. 이렇게 제곱의 수와 3진법의 수를 계속 곱하고 더하면 10진법으로 변환할 수 있다.

 

 

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/68935

프로그래머스