[백준] 4673번 셀프넘버 - Java(자바)

4673번(solved.ac 난이도 실버5)

셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다.
양의 정수 n이 주어졌을 때, 이 수를 시작해서 n, d(n), d(d(n)), d(d(d(n))), ...과 같은 무한 수열을 만들 수 있다.
예를 들어, 33으로 시작한다면 다음 수는 33 + 3 + 3 = 39이고, 그 다음 수는 39 + 3 + 9 = 51, 다음 수는 51 + 5 + 1 = 57이다. 이런식으로 다음과 같은 수열을 만들 수 있다.
33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, ...
n을 d(n)의 생성자라고 한다. 위의 수열에서 33은 39의 생성자이고, 39는 51의 생성자, 51은 57의 생성자이다. 생성자가 한 개보다 많은 경우도 있다. 예를 들어, 101은 생성자가 2개(91과 100) 있다.
생성자가 없는 숫자를 셀프 넘버라고 한다. 100보다 작은 셀프 넘버는 총 13개가 있다. 1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 97
10000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 출력하는 프로그램을 작성하시오.

 

난 이렇게 생각했다.

문제를 읽고 맨 처음 생각난 풀이는 어떻게 셀프넘버를 계산할지는 모르겠지만, 1부터 10000까지 저장된 ArrayList 를 만들고, 1부터 10000까지 차례대로 계산한 셀프넘버를 이 ArrayList 에서 빼면 생성자가 없는 숫자를 구할 수 있을거라 생각했다. 계산된 셀프넘버는 즉 생성자가 있다는 말이니까.
1부터 시작했다 했을때 d(1) = 1+1 = 2 가 되고 2의 생성자는 1이다. 1부터 10000까지 저장된 리스트에서 2를 빼면 1,3,4,5,6 ... 이 된다.
d(2) = 2+2 = 4, 리스트에서 4를 빼면 1,3,5,6,7,8,9.... 가 된다.
d(1) 부터 d(10000)까지 계산하여 그 결과를 리스트에서 제거하면 최종적으로 리스트에 남는 숫자는 생성자가 없는 숫자이다.
그렇다면 셀프넘버를 어떻게 계산할까?
이 또한 처음에는 자리수만큼 나머지 계산을 하여 원래 숫자에 각 자릿수를 더해주면 되지 않을까? 하고 간단하게 생각했다.
물론 문제에서 10000까지 라고 주어졌으니 숫자 크기를 판별하여 나누어질 자리수를 코드로 정해줄 수도 있었겠지만, 그것보다 나는 형변환을 좀 많이하더라도 문자열로 바꿔서 각 자릿수를 인덱스로 접근하는 방법을 선택했다.
단, String.charAt(int index)를 사용하여 나온 결과는 char 형이고, 숫자는 아스키코드에 대응되어 그냥 더해주면 48~57이라는 값이 더해지므로 0에 해당하는 48을 빼주어 온전한 숫자를 얻었다.(가령 '3'일 경우 아스키코드에 대응되는 값이 51이므로 51-48 = 3 이 되어 숫자 3을 얻을 수 있다. 어차피 0부터 9까지만 나올거니까)
이제 셀프넘버도 구했고, 알고리즘도 생각했으니 코드로 짜는일만 남았는데..

처음에 리스트에 존재하면 제거하라는 코드를 아래와 같이 짰더니 에러는 아니지만 원하는 결과가 나오지 않았다.

            if (arr.contains(result))
                arr.remove(result);

이유는 ArrayList.remove()에 int값을 넣게 되면 인덱스로 인식하여 ArrayList의 result값을 제거하는것이 아닌 result위치의 엉뚱한 값을 제거하고 있었기 때문이다.
따라서 Integer.valueOf(result)를 해주어 result값 Integer객체 자체를 넘겨주었다.


누가 볼지 모르겠지만, 코드를 보기 싫은 사람을 위해 공백을 좀 두고 아래에 코드를 쓰겠다. 혹시 여기까지 보고 직접 짜보고 싶은 사람도 있을테니...(사실 내가 그렇다. 도저히 안풀리는 문제에 대해 온전한 코드보다 풀이를 먼저 보고싶어한다. 나같은 사람도 있을수 있잖아..)










내가 푼 코드는 다음과 같다.

import java.util.*;
public class Main {
    static ArrayList<Integer> arr;
    public static void main(String[] args) {
        arr = new ArrayList<>();
        // 시작시 1부터 10000까지 들어있는 배열 생성. 재귀함수로 10000을 입력하면 10000이 될때까지 함수 d(n) 실행. 
        for (int i = 0; i < 10000; i++)
            arr.add(i + 1);
        checkSelfNum();

    }
    static void checkSelfNum() {
        for (int i = 1; i <= 10000; i++) {
            int result = i;
            for (int k = 0; k < Integer.toString(i).length(); k++) {
                result += Integer.toString(i).charAt(k)-'0'; // char 로 잘랐을때 아스키코드 값이 아닌 온전한 숫자를 얻고 싶었음
            }
            if (arr.contains(result))
                arr.remove(Integer.valueOf(result)); // result가 int 이므로 index로 받아들여지기 때문에 result의 값 자체를 객체로 전달함
            else
                continue;
        }
        for(int i=0;i<arr.size();i++)
            System.out.println(arr.get(i));
    }
}

결과는 정답이다.