Programmers 3진법 뒤집기

문제 설명

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

제한사항
  • n은 1 이상 100,000,000 이하인 자연수입니다.
입출력 예
n result
45 7
125 229
입출력 예 설명

입출력 예 #1

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

입출력 예 #2

  • 답을 도출하는 과정은 다음과 같습니다.
n (10진법) n (3진법) 앞뒤 반전(3진법) 10진법으로 표현
125 11122 22111 229
  • 따라서 229를 return 해야 합니다.

최초 생각했던 풀이 방법

  1. 자연수 n을 ToCharArray()로 char [] 바꾸기
  2. 바뀐 char[]을 Convert.ToString(char[], 3);로 3진수로 변경한다
  3. 변경된 3진수의 char[]을 Array.Reverse(char[]) 로 배열을 뒤집는다.
  4. 변경된 값을 foreach로 string 으로 합쳐 준다.
  5. 뒤집은 배열을 다시 Convert.ToString(char[], 10)으로 10진수로 변경하여 반환한다.
public int solution(int n) 
{ 
	string strngArray = ""; 
	char[] terary = Convert.ToString(n, 3).ToCharArray(); 
	Array.Reverse(terary); 
	foreach (var c in terary) 
	{ 
		strngArray += c; 
	} 
	int tens = Convert.ToInt32(strngArray, 10); 
	return tens; 
}
발생 Error
Unhandled Exception: System.ArgumentException: Invalid Base. 
at System.Convert.ToString (System.Int32 value, System.Int32 toBase) 

[0x00012] in <de882a77e7c14f8ba5d298093dde82b2>:0 at Solution.solution (System.Int32 n) 
[0x00006] in <1692f965f4ff446b8193cb83907837d8>:0 at SolutionTest+<Main>c__AnonStorey0.<>m__0 () 
[0x00000] in <1692f965f4ff446b8193cb83907837d8>:0 at CodeRunner.SolutionRunner.Run (System.Func`1[TResult] f) 
[0x0000c] in<a4441186f3ad4699b2a3ca0b05651699>:0 at SolutionTest.Main (System.String[] args) 
[0x00035] in <1692f965f4ff446b8193cb83907837d8>:0 

[ERROR] FATAL UNHANDLED EXCEPTION: System.ArgumentException: Invalid Base. 
at System.Convert.ToString (System.Int32 value, System.Int32 toBase) 
[0x00012] in <de882a77e7c14f8ba5d298093dde82b2>:0 at Solution.solution (System.Int32 n) 
[0x00006] in <1692f965f4ff446b8193cb83907837d8>:0 at SolutionTest+<Main>c__AnonStorey0.<>m__0 () 
[0x00000] in <1692f965f4ff446b8193cb83907837d8>:0 at CodeRunner.SolutionRunner.Run (System.Func`1[TResult] f) 
[0x0000c] in <a4441186f3ad4699b2a3ca0b05651699>:0 at SolutionTest.Main (System.String[] args) [0x00035] in <1692f965f4ff446b8193cb83907837d8>:0
  • 위의 문제는 Convert.ToString(int32 value, int32Base) 에서 문제가 발생했다는 것
  • 처음 Convert.ToString의 겨우 base에 따라서 해다 진수로 변경해준다고 알고 있었음
  • 하지만 ConvertToString의 경우 2,8,10,16진수에 대해서만 변경이 가능했다.
  • 반대로 3진수에서 10진수로의 변형도 불가하다

해결 방법

3진수, 10진수 를 변혈 할 수 있는 함수를 별도로 만들기

3진수 변형

10진수를 3진수로 변경하는 방법

  • 연속적으로 주어진 10진수를 3으로 나누고,
  • 그 나머지를 임시저장하고,
  • 몫을 다시 3으로 나누고 그 나머지를 다시 더해주는 방식으로
  • 더이상 나눌 수 없을 때 까지 실행한다
n = 45 일때

45 % 3   / 몫 : 15 나머지 : 0
15 % 3   / 몫 : 5  나머지 : 0
 5 % 3   / 몫 : 1  니머지 : 2
 1 % 3   / 더이상 나누어 지지 않으므로 중지 나머지 : 1

45 => base : 3 => 1200
10 진수 변형

각 자릿수에 해당하는 3의 거듭제곱을 곱하고, 그 결과를 모두 더하기

$2102{(3)}$ 진수 를 10진수로 바꾸는 예시

$가장 오른쪽 자리 (1의 자리) : 2 \times 3^0 = 2$

$다음 자리 (3의 자리) : 0 \times 3^1 = 0$

$다음 자리 (9의 자리) : 1 \times 3^2 = 9$

$가장 왼쪽 자리 (27의 자리) : 2 \times 3^3 = 54$

$54 + 9 + 0 + 2 = 65$

따라서 $2102{(3)진법}$ 은 ${(10)진법}$ 으로 $65$ 이다.

문제 해답

Base(10) => Base(3) Convertor

private string ConvertToBase3(int num)
{
	string base3 = "";
	
	while (num > 0)
	{
		base3 = (num % 3) + base3;
		num /= 3;
	}
	return base3;
}
  • Base3의 빈 String 값을 선언
  • whil문으로 3진법을 구하는 식을 작성

Base(3) => Base(10) Convertor

private int ConvertToBase10(char[] base3)
{
	int base10Sum = 0;
	int pow = base3.Length - 1;

	for (int i = 0; i < base3.Length; i++)
	{
		int digit = base3[i] - '0';
		base10Sum += digit * (int)Math.Pow(3, pow);
		pow--;
	}
	return base10Sum;
}
  • 제곱(pow)는 가장 마지막 자리는 $3^0$ 이므로 -1을 해준다.
  • 3진수의 길이만큼 Loop를 시킨다
  • $3^{(i)}$ 는 char ‘0’을 빼서 정수로 만들어 준다.
    • ‘0’ - ‘0’ = 0;
    • ‘0’ - ‘0’ = 0;
    • ‘2’ - ‘0’ = 2;
    • ‘1’ - ‘0’ = 1;
  • 정수에 $3^{(i)}$ 을 큰 자릿수부터 차례로 차감하며 자릿수를 채운다

    $1 \times 3^0 = 1$

    $2 \times 3^1 = 6$

    $0 \times 3^2 = 0$

    $0 \times 3^3 = 0$

$0 + 0 + 6 + 1 = 7$

변환식

public int solution(int n)
{
	char[] ternary = ConvertToBase3(n).ToCharArray();
	Array.Reverse(ternary);
	return ConvertToBase10(ternary);
}

Solution 전체 스크립트

using System;
using System.Linq;

public class Solution 
{
	public int solution(int n)
	{
		char[] ternary = ConvertToBase3(n).ToCharArray();
		Array.Reverse(ternary);
		return ConvertToBase10(ternary);
	}


	private string ConvertToBase3(int num)
	{
		string base3 = "";
		
		while (num > 0)
		{
			base3 = (num % 3) + base3;
			num /= 3;
		}
		return base3;
	}

	private int ConvertToBase10(char[] base3)
	{
		int base10Sum = 0;
		int pow = base3.Length - 1;
	
		for (int i = 0; i < base3.Length; i++)
		{
			int digit = base3[i] - '0';
			base10Sum += digit * (int)Math.Pow(3, pow);
			pow--;
		}
		return base10Sum;
	}
}

Best Code

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;
    }
}

  1. answer *= 3;: 이 라인은 현재 answer에 저장된 값을 3배로 증가시킵니다. 이 연산은 answer에 이미 저장된 모든 자릿수를 한 자리씩 왼쪽으로 이동시키는 것과 같습니다. 처음에는 answer가 0이기 때문에 영향을 주지 않지만, 루프가 반복될 때마다 현재까지의 결과에 3을 곱하여 새 자릿수를 추가할 공간을 만듭니다.

  2. answer += n % 3;: n % 3 연산은 n을 3으로 나눈 나머지를 계산합니다. 이 나머지는 현재 n의 가장 낮은 자리 3진수 자릿수에 해당합니다. 이 값을 answer에 더함으로써, answer의 가장 오른쪽에 새 자릿수를 추가합니다. 이는 뒤집힌 3진수에서 다음으로 가는 과정입니다.

  3. n /= 3;: 마지막으로 n을 3으로 나누어 줌으로써, n에서 가장 낮은 자릿수를 제거합니다. 이는 n이 3진수로 전환되면서 한 자릿수씩 처리되도록 하기 위함입니다.

루프가 반복될 때마다, 이 세 단계를 거치면서 n의 각 자릿수가 뒤집힌 순서로 answer에 저장됩니다. 이 과정은 n이 0이 될 때까지, 즉 모든 자릿수가 처리될 때까지 계속됩니다.

실제로 이 알고리즘은 입력된 10진수를 뒤집힌 3진수로 변환하는 과정이며, 그 결과로 3진수를 10진수로 다시 변환하지 않고도 원하는 결과를 얻을 수 있습니다.

코드 로직의 작동 시뮬레이션

n = 45

Start

1. $answer = 0$

Loop 1.

$answer = 0 \times 3 + 0 = 0$

$answer = 0$

$n = 45 \div 3 = 15$

$n = 15$

Loop2

$answer = 0 \times 3 + 0 = 0$

$answer = 0$

$n = 15 \div 3 = 5$

$n = 5$

Loop3

$answer = 0 \times 3 + 2 = 2$

$answer = 2$

$n = 5 \div 3 = 1$

$n = 1$

Loop4

$answer = 2 \times 3 + 1 = 7$

$answer =\’ \ \ 7 \ \ ‘$

$n = 1 \div 3 = 0$

$n = 0 => Loop Escape$

진짜 어마어마 하다