[문제해결을 위한 창의적 알고리즘] 숫자 뒤집기 (고급 p.83)

이 책의 동적 계획법 (Dynamic Programming)의 첫번째 문제로 이 문제가 등장한다. 앞에서도 등장했던 문제로, 풀이를 보면 이 문제를 왜 이렇게 풀어야 하는지 조금 의심스럽긴 하다. 계산량이 줄어든다고 보기도 어렵고, 주어진 n까지 (최대 50,000) 메모리를 확보해야 한다.

앞선 포스트 ([문제해결을 위한 창의적 알고리즘] 숫자 뒤집기 (고급, p18))에서도 풀이를 한 적이 있지만, 다시 한번 풀이를 작성해 보았다. 또한 pow()와 log10()는 직접 구현하여 라이브러리 참조를 최소화하였다. 나머지 부분은 풀이를 참고하기 바란다.

import java.util.Scanner;

public class ReverseNumSol84 {

// 최대 숫자까지 다이나믹 테이블 선언

public static int[] DT= new int[50001];

// 밑이 10인 로그 함수

public static int log10(int n){

int i;

for (i=0; n/10>0;i++)

n/=10;

return i-1;

}

// a를 b 거듭제곱한 값을 반환

public static int pow(int a, int b){

int i;

for (i=0; i <b; i++)

a*=10;

return a;

}

public static void main(String[] args) {

int n, i;

Scanner sc = new Scanner(System.in);

n = sc.nextInt();

sc.close();

for (i =1; i<=n; i++){

if (i <10)

DT[i]=i;

else

DT[i]=DT[i/10]+(i%10)*(int)pow(10,(int)log10(i));

}

System.out.println(DT[n]);

return;

}

}

Big O(n):n은 숫자 자릿수

Github: https://github.com/nevermet/CreativeAlgorithmAdv/blob/master/ReverseNumSol84.java

문제해결을 위한 창의적 알고리즘 목록