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

문제 내용

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

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

124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다.

1. 124 나라에는 자연수만 존재합니다.
2. 124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다.

예를 들어서 124 나라에서 사용하는 숫자는 다음과 같이 변환됩니다.

10진법124 나라10진법124 나라

1	1	6	14
2	2	7	21
3	4	8	22
4	11	9	24
5	12	10	41

자연수 n이 매개변수로 주어질 때, n을 124 나라에서 사용하는 숫자로 바꾼 값을 return 하도록 solution 함수를 완성해 주세요.

 

제한사항

• n은 500,000,000이하의 자연수 입니다.

 

입출력 예

nresult

1	1
2	2
3	4
4	11

 

---

문제 접근 방법

처음에 제한사항을 고려하지않고 그냥 매개변수 n만큼 순회하면서 각 숫자를 치환하는 작업을 했는데 당연히 틀렸다.

틀린 이유는 단순히 어떤 숫자가 들어오든 1~10을 치환하기만 했었고 무엇보다 최악의 경우 n이 500,000,000이면 5억번 돌아야해서 로직이 맞아도 진짜 오래걸릴꺼 같다.

 

그래서 이런 문제는 규칙이 무조건 존재하는 그 규칙을 찾는게 관건이다.

하지만 나는 찾지 못해서 다른 사람들 블로그를 통해 규칙이 뭔지 알아 냈다.

 

규칙은 다음과 같다.

 

1. 1 , 2 , 4를 담고 있는 배열 nums가 있을때 n%3의 값은 nums의 인덱스와 같다.

2. 즉 n%3 이 0, 1, 2 일때  nums 배열은 {4, 1, 2} 가된다.

3. n%3을 해서 인덱스를 x를 구하면 nums[x]를 answer에 값을 추가한다.

4. 그리고 n을 재할당 해주는데 n = (n-1)/3을 해준다.

5. 3~4번 과정을 n>0인 동안 반복한다.

 

풀이를 보자.

 

---

풀이

틀린 코드

public class country124 {
	public static void main(String[] args) {
		int n = 10987;
		solution(n);
	}
	
	public static String solution(int n) {
		HashMap<String, String> map = new HashMap<String, String>();
		StringBuilder sb = new StringBuilder();
		String[] con124 = {"1","2","4","11","12","14","21","22","24","41"};
		for(int i=0; i<con124.length; i++) {
			map.put(Integer.toString(i+1), con124[i]);
		}
		
		String num = Integer.toString(n);
		for(int i=0; i<num.length(); i++) {
			String st = String.valueOf(num.charAt(i));
			if(st.equals("0")) {continue;}
			
			if(st.equals("1") && i<num.length()-1) {
				String st2 = st+String.valueOf(num.charAt(i+1));
				if((st2).equals("10")) {
					sb.append(map.get(st2));
				}
			}else {
				sb.append(map.get(st));
			}
		}
		//10987
		//41242221
		System.out.println(sb.toString());
		return sb.toString();
	}
}

 

정답 코드

public class country124_2 {
	public static void main(String[] args) {
		int n = 10987;
		solution(n);
	}
	
	public static String solution(int n) {
		String answer = "";
		String[] nums = {"4", "1", "2"};
		
		while(n>0) {
			answer = nums[n%3] + answer;
			n = (n-1)/3;
		}
		
		System.out.println(answer);
		return answer;
	}
}

 

---

마무리

이런문제는 규칙을 찾아내면 쉽게 풀수 있는 문제이다. 하지만 그 규칙을 찾는게 많이 해보지 않으면 너무 어려운...ㅠ

여튼 여기 규칙에서는 n%3이 핵심인데 3으로 나누는 이유는 값이 1,2,4 세개이고 나머지는 무조건 0,1,2 세개중 하나만 나오기 때문이 아닐까.. 주관적인 생각을 해본다..!