(알고리즘 스터디) 9주차 수_(Programmers) 124 나라의 숫자

🌟 프로그래머스 / Level 2 / 124 나라의 숫자

📃 문제

프로그래머스

🚫 제한 사항

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

👀 입출력 예

n	result
1	1
2	2
3	4
4	11

🤔 풀이 방법

1️⃣ 조합

① 아이디어

➡️ 기본적으로 숫자들의 형태가 중복 조합과 같은 형태라고 생각했다.

ex) n = 4 ➡️ "11" / tmp = 0
① 문자열의 길이를 구한다. / 4 일 때 문자열의 길이 : 2
② 그 전 형태들의 값을 구한다. / "1", "2", "4" ➡️ 3 개 (tmp = 3)
③ 깊이가 4 인 형태들의 조합들을 확인하면서 tmp 값과 n 이 같아질 때까지 반복한다.

② 코드

class Solution {
    public static int depth = 1;
    public static int tmp = 0;
    public static String answer = "";
    public static boolean stop = false;
    public static String[] str;
    public static String[] nums = {"1", "2", "4"};
    
    public String solution(int n) {
        // 문자열의 길이 확인
        int cnt = 3;
        while (n > cnt) {
            cnt += Math.pow(3, ++depth);
        }
        
        // 배열 생성
        str = new String[depth];
        
        // 그 전까지의 조합의 개수
        for (int i=1; i<depth; i++) {
            tmp += Math.pow(3, i);
        }
        
        // 조합 확인 & 결과 출력
        comb(n, 0);
        
        return answer;
    }
    public static void comb(int n, int d) {
        if (d == depth) {
            tmp++;
            
            if (n == tmp) { // 내가 찾는 순서면 문자열 생성 후 반환
                for (String st : str) {
                    answer += st;
                }
                stop = true;
            }
            return;
        }
        for (int i=0; i<3; i++) {
            str[d] = nums[i];
            // 찾았으면 더 탐색할 필요가 없으므로 바로 종료
            if (stop) return;
            comb(n, d+1);
        }
    }
}

③ 결과

 

정확성 테스트 100% 통과

효율성 테스트 100% 실패

➡️ 아무래도 입력값 n 이 커질 수록 재귀도 많아지면서 시간 초과로 실패하게되는 것 같았다. 이를 해결하기 위해서는 일단 조합 (재귀) 를 포기해야한다.

2️⃣ 규칙 찾기

➡️ 재귀를 사용하지 않는다면 결국에는 수학적으로 규칙을 찾아내는 방식이라고 생각했다. 일단 아래와 같은 접근을 해보았다.

① 3진법은 0, 1, 2 로 숫자 0 부터 표현한다.
② 현재 문제는 1, 2, 4 로 1 부터 표현한다.
➡️ 3진법을 적용시킬려면 구하려는 수 n 에서 1을 빼서 0부터 시작한 후 수를 변환해야한다. (0 ➡️ 1, 1 ➡️ 2, 2 ➡️ 4)

실제로 위 풀이를 적용시켰을 때 1부터 9까지는 잘 구해졌다. 하지만 10부터는 해당 풀이가 적용되지 않았다. 이유를 생각해보니 124 나라의 법칙으로는 3자리로 넘어갔을 때 첫자리에 모든 수를 배치할 수 있지만 3진법에서는 0 을 제외한 1, 2 만 배치 가능하기 때문에 완벽한 변환이 어려운 거였다. 이 때부터 내가 할 수 있는 수학적 규칙 찾기는 끝났다고 생각했고 그냥 질문하기를 통해 효율성 테스트를 통과한 코드를 확인해보았다.

👀 <질문하기>를 통해 확인한 규칙
① 구하려는 수 n 을 3으로 나눈다.
② 나머지를 확인한다
②-(1) 나머지가 0인 경우 ➡️ 몫은 -1 / 나머지는 4로 해준다.
②-(2) 나머지가 0이 아닌 경우 ➡️ ③ 으로 넘어간다.
③ 나머지를 StringBuilder 에 append 한다. / sb.append(나머지 or 4);
④ 거꾸로 출력되어야하므로 reverse를 적용한다.  / sb.reverse();
⑤ 마지막 몫이 0이 아니면 맨 앞에 붙여준다. / sb.insert(0, 몫);
⑥ 문자열로 변환하여 반환한다. / return sb.toString();

② 코드

import java.util.List;

class Solution {
    public String solution(int n) {
        StringBuffer sb = new StringBuffer();
	// ①
        while(n >= 3) {
            int q = n / 3;
            int r = n % 3;
	// ②
            if(r == 0) {
                q = q-1;
                r = 4;
            }
            
            n = q;
	// ③
            sb.append(r);
        }
	// ④
        sb.reverse();
	// ⑤
        if (n != 0) {
            sb.insert(0, n);
        }
	// ⑥
        return sb.toString();
    }
}

③ 결과

➡️ 테스트 케이스와 효율성 테스트 모두 짧은 시간 안에 통과하였다. 하지만 이게 코딩 문제인지 수학 문제인지 모르겠다...

💻 풀이 코드

[level 2] Title: 124 나라의 숫자, Time: 0.16 ms, Memory: 52.8 MB -BaekjoonHub · Young998904/Practice_Algorithm_Auto@d3fb45