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

programmers.co.kr/learn/courses/30/lessons/12899

코딩테스트 연습 - 124 나라의 숫자

알고나면 어렵지 않아보이지만 막상 접근하기 쉽지 않았던 문제였다.

일단, 접근 방법이 떠오르지 않아서 다른 사람의 풀이를 참조했다.

 

n이 5억이다.

적어도 O(N)으로는 풀 수 없는 문제라는 얘기이다.

따라서, 규칙을 찾아서 풀어야하는데

일단 3으로 나눠본다.

나눴더니 어느정도 규칙이 보인다.

나머지가 0일 때 4, 1일 때 1, 2일 때 2이다.

여기까지는 생각했는데 두 자리 숫자가 되면 어떻게 되지에서 막혀버렸다.

 

풀이는 간단하다.

우리가 흔히 알고 있는 10진수를 2진수로 바꾸는 방법처럼 풀면 된다.

몫이 0이 될 때까지 나눈 후에 나머지를 거꾸로 나열한다.

대신, 0일 때는 값이 4이고 n을 1만큼 빼줘야한다.

거꾸로 나열할 때 answer를 뒤에 다 +연산해주는 방법은 기발한 것 같다.

 

public String solution(int n) {
		String[] numbers = { "4", "1", "2" };
		String answer = "";
		
		int num = n;
		while(true) {
			if(num == 0) {
				break;
			}
			int remain = num%3;
			num /= 3;
			if(remain == 0) num--;
			
			answer = numbers[remain] + answer;
		}
		
		return answer;
    }

 

 

 

 

velog.io/@hyeon930/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-124-%EB%82%98%EB%9D%BC%EC%9D%98-%EC%88%AB%EC%9E%90-Java

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