[프로그래머스] 124 나라의 숫자

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/12899

코딩테스트 연습 - 124 나라의 숫자 | 프로그래머스

코드

package Programmers.Level2;

public class OneTwoFourNumber {

	public static void main(String[] args) {

		int n = 10 ;
		
		String answer = solution(n);
		
		System.out.println(answer);


	}//main

	  public static String solution( int n ) {
	      
	      String answer = "";
	      
	      String[] special = { "4","1","2" } ;
	      
	      while ( n != 0 ) {
	    	  int nmg = n%3 ;
	    	  answer = special[nmg] + answer ;
	    	  n/=3;
	    	  if ( nmg == 0 ) n-=1;
	      }
	      
	      return answer;      
	  }
}//class

제출 결과

후기

3진법으로 해결해야 한다는 것은 스스로 생각하지 못했다..

 

왜 3진법인가?? 를 이해하려고 노력하였다.

 

문제와 3진법의 공통점은 [ 0,1,2 ] 나 [ 1,2,4 ]의 3개의 숫자로 10진수를 표현한다는 것이다.

 

10진수를 각각 3진수와 124의 수로 표현하면 위의 표와 같다.

 

처음에는 10(3)은 밑을 3으로 계산해나가면 3이 나오는데, "4(124)는 밑을 무엇으로 해야 되는가?.."를 고민했다. 포인트를 잘못 잡고 있었던 것이다. 실제 변환된 124수의 값이 어떻게 10진수가 되는지는 중요하지 않았다.

 

10진수를 어떻게 (124) 숫자로 표현하는가?? 가 이문제의 포인트였다..

 

규칙을 찾아보면 숫자가 커 짐에 따라 1,2,4라는 숫자가 규칙적으로 사용되며 표현되고 있다. 3진수도 그렇다 0,1,2가 규칙적으로 사용된다.

 

3진수를 만드는 방법은 정수 N을 3으로 나눈 나머지를 붙여나가면 만들 수 있다.

 

(124) 숫자도 똑같다 정수 N을 3으로 나눈 나머지를 붙여나가면서 만들면 된다.

 

그런데 단지, "0이란 숫자를 4로 바꾸면 되는 건가?" 라는 의심이 들었다..

 

바꿔도 된다!라는 결정을 하게 된 근거는 아래와 같다.

 

10진수 1,2,3을 3으로 나눈 나머지가 무엇인가?로 보자.

 

표에서 볼 수 있듯이 나머지가 1이면 3진수, (124) 숫자 모두 1이다. 2이면 2이다 , 0이면 3진수는 10을 (124) 숫자는 4이다.

 

고로 나머지가 0인 경우에는 4를 출력해주면 된다.

 

그러나 단순히 3으로 나눈 나머지를 출력하게되면 문제가 생긴다. 10진수 3을 동일한 방식으로 3진수와 (124)숫자를 구해보면 문제에 주어진 값과, 내가 정의 한 알고리즘의 출력이 다르다는 것을 볼 수 있다.

 

10진수 3을 변환하는 과정은 아래와 같다.

 

N = 3일 때, N이 0이 될 때까지 나머지를 맨 앞에 넣어준다. N은 계속3으로 나누어간다.

 

3 % 3 = 0 >>> 맨앞에 넣어준다.

N = N/3 >>> 1이 된다.

 

1 % 3 = 1 >>> 맨앞에 넣어준다.

N = 1/3 >>> 0이 된다.

 

고로 10(3)이 된다.

 

동일하게 (123) 숫자를 적용해 보자.

 

3 % 3 = 0 >>> 0은 4로 바꿔줘야 함을 찾았다. 고로, 4를 맨 앞에 넣어준다.

N = N/3 >>> 1이 된다.

 

1 % 3 = 1 >>> 맨앞에 넣어준다.

N = 1/3 >>> 0이 된다.

 

고로 04(124)가 된다.

 

문제에 주어진 10진수 3의 124 숫자는 04가 아닌 4이다. 즉, 다른 답이 나오게 된다.

 

이 문제를 어떻게 해결할 수 있을까?? 를 또 고민하였다.

 

해결방법을 찾기 위해서 나머지가 0이 되는 경우가 존재하는 숫자들 ( 단순히 3의 배수들 )을 찾아서 비교해 보았다.

 

다른 풀이를 보았을 때 왜 N-1을 해주는지 몰랐다.. 그렇다고 나도 아! 하고 떠오르지도 않았다..

 

그래서 직접 연산을 하고 비교해보면서 답이 되도록 시도해보았고, 그렇게 답을 찾았다..

 

다른 블로그의 풀이는 "간단합니다."라는 식의 글이 많았지만 내가 스스로 그 방법을 생각해낼 수 있었을까를 고민해보면.. 지금의 나에게는 결코 간단하지 않았을 문제인 것 같다..