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

📝24.01.22

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

문제 설명

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

[C#] 내가 작성한 풀이

문제에 제시된 순서에 따라 10진법을 3진법의 거꾸로 된 모습으로 바꾸고, 다시 10진법으로 바꾸어주는 알고리즘으로 풀이했다.

using System;

public class Solution {
    public int solution(int n) {
        int answer = 0;
        
        string s = "";
        while(n > 0) {
            s += (n % 3).ToString();
            n /= 3;
        }
        
        int length = s.Length - 1;
        
        for(int i = 0; i < s.Length; i++) {
            answer += int.Parse(s[i].ToString()) * (int) Math.Pow(3, length - i);
        } 
        return answer;
    }
}

[C#] 남이 작성한 풀이

충격적으로 간단한 알고리즘이 있었다.

위의 풀이를 작성하면서 알아낸 것은, 3으로 나누었을 때의 나머지를 순서대로 작성하면 그대로 3진법으로 바꾼 것의 거꾸로 된 숫자를 얻을 수 있다는 것이다. 그리고 나는 그것을 한 번 더 자릿수 별로 3의 거듭제곱값을 곱해주기위해 또 for 반복문을 사용했다.

하지만, 단순히 생각해보면 그냥 나머지 수를 3배씩 반복하면 3진수의 자릿수에 3배가 된다. 이를 활용한 풀이가 바로 아래의 풀이다.

using System;

public class Solution {
    public int solution(int n) {
        int answer=0;
    	while(n>0){
        	answer*=3;
        	answer+=n%3;
        	n/=3;
    	}
        
    	return answer;
    }
}

이 풀이를 보고 C++은 동일한 풀이로 풀었다.

[C++] 남이 작성한 풀이

C#의 내가 한 풀이에서 사용한 string을 vector로만 바꾼 풀이라고 볼 수 있다.

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    vector<int> v;
    while(n > 0){
        v.push_back(n%3);
        n/=3;
    }
    int k = 1;
    while(!v.empty()) {
        answer += k*v.back();
        v.pop_back();
        k*=3;
    }

    return answer;
}