20231110_기록_3진법 뒤집기(프로그래머스)

오늘 한 것들

 

알고리즘 코드카타 40. 3진법 뒤집기

Chapter 2 프로그래밍기초 개인과제

 

오늘 TIL은 3진법 뒤집기로 아래 링크의 문제이다.

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

 

프로그래머스

 

문제를 정리하면

 

주어진 숫자 n을 3진수로 변환(a)

변환된 3진수의 수(a)를 역순으로 재배열(b)

재배열된 수(b)를 10진수로 변환(c)하여 이를 출력하는 문제이다.

 

정답 코드

public int solution(int n) {
        int answer = 0;
        string str1 = ConvertToTernary(n);
        string str2 = new string(str1.Reverse().ToArray());
        answer = ConvertFromTernary(str2);
        
        return answer;
    }
    
    private string ConvertToTernary(int number)
    {
        if (number == 0) return "0";
        string result = "";
        while (number > 0)
        {
            result = (number % 3) + result;
            number = number / 3;
        }
        return result;
    }
    
    private int ConvertFromTernary(string number)
    {
        int result = 0; 
        for (int i = 0; i < number.Length; i++)
        {
            int digit = number[i] - '0';
            result = result * 3 + digit;
        }
        return result;
    }

 

이 논리를 따라가면 3줄이면 끝날 것으로 생각한 문제였지만,

C#에서 숫자를 3진수로 표현하는 기능이 없기 때문에, 이를 직접 구현해야되었다.

따라서 3진수로 표현하는 방법을 다시 생각해봐야되는데

정수 n을 3진수로 표현하는 방법은 아래의 그림을 따라가면 된다.

 

 

정수 n을 3으로 몫이 0이 될 때까지 나누고

각각 나온 나머지의 값을 가지고 3진수로 표현하는데

처음에 나온 자릿수가 가장 작은 자릿수가 되게, 마지막에 나온 나머지가 가장 큰 자릿수가 되게 정리하면 된다.

 

 

예를 들어 256을 3진수로 나타내면 아래와 같은데

 

 

256을 3으로 나눈 몫 85가 다음 나눌 대상이 되고, 나머지 1이 가장 뒷자릿수가 된다.

이렇게 계산하는 과정을 코드로 나타내면 아래와 같다.

 

private string ConvertToTernary(int number)
    {
        if (number == 0) return "0";
        string result = "";
        while (number > 0)
        {
            result = (number % 3) + result;
            number = number / 3;
        }
        return result;
    }

 

여기서 핵심은 result를 string으로 하는 것으로

3으로 나눈 나머지들을 문자로 처리하여 순서대로 붙이는 것이다.

또, 그 더하는 위치가 왼쪽에 새 숫자가 나오게 함으로써

위의 그림에서 빨간색의 화살표의 순서로 숫자를 붙여나가는 것이다.

 

이렇게 하면 result로 나오는 n을 string의 3진수로 표현한 것이 된다.

 

이후에 이 result를 역순으로 정리하기 위해 아래의 순서를 진행한다.

string str2 = new string(str1.Reverse().ToArray());

 

 

이제 역순으로 정리한 3진수를 다시 10진수로 변환해야되는데,

여기서도 바로 10진수로 변환하는 방법이 없어 함수로 표현해야된다.

 

3진수의 숫자를 10진수로 변환하는 것은 위의 그림에서 적혀있듯이

100111(3)인 경우

1*(3^5) + 0*(3^4) + 0*(3^3) + 1*(3^2) + 1*(3^1) + 1*(3^0) = 256으로 구할 수 있다.

따라서 result를 이에 따라 더하는 식을 만들면 아래와 같다.

 

private int ConvertFromTernary(string number)
    {
        int result = 0; 
        for (int i = 0; i < number.Length; i++)
        {
            int digit = number[i] - '0';
            result = result * 3 + digit;
        }
        return result;
    }

 

여기서 특징적인 점은 digit을 int로 변환하는 과정에서 '0'을 빼는 것인데,

number[i]는 string이기 때문에 string을 int로 변환하는 과정에서

'0'에 해당하는 값을 빼야 우리가 아는 숫자 값으로 바꿀 수 있다.

(처음에 이 이유를 몰라서 값이 이상하게 변환되어 이를 해결하는데도 고생했다)

 

 

오늘은 간단해보였지만 실제로 풀이하는데 오랜 시간이 걸린 3진수 뒤집기를 했는데,

이를 응용하여 3진수가 아닌 N진수도 같은 방식으로 진행할 수 있을 것으로 생각된다.