[JAVA] 백준 4673 셀프 넘버

그린·2024년 3월 4일

PS

목록 보기

4/17

1) 문제

https://www.acmicpc.net/problem/4673

2) 문제 접근

실은 1년 전에 풀어봤던 문제였긴 한데,,
기억은 안 났다,,

그냥 브루트포스로 일일이 돌면서 파악하는 방법밖에 생각해내지 못했는데
풀고나서 예전 풀이랑 다른 분 풀이를 찾아보니 맞는 방법이긴 했다.

나는 numbers라는 0 ~ 10001 크기의 boolean 배열을 선언했다.
numbers는

셀프넘버가 아닌 경우 : true
셀프넘버인 경우 : false
로 담기도록 의도했다.

1 ~ 10000 번 인덱스에 대해 다 돌면서
해당 인덱스 값 n에 대해 d(n) 을 구한 후
d(n)이 10000보다 작으면
셀프넘버가 아닌 10000보다 작은 수 이므로, numbers[d(n)] = true 로 넣어줬다.

이때 d(n)을 구하기 위해,
39 -> 39 + 3 + 9 = 51 이 되어야 하는 만큼

next_num(51이 되고자 하는 변수)와
temp_num(39에서 3, 9 이렇게 한 자리 수만 가져오기 위한 변수)을

활용해서 d(n)을 구했다.

3) 풀이 1

메모리: 14512 KB, 시간: 156 ms

이리저리 수정해가면서 정답이 나온 코드인데, 살짝 지저분하다..

public class Main {
    public static void main(String[] args) {
        boolean[] numbers = new boolean[10001];
        for (int i = 1; i <= 10000; i++) {
            int next_num = i;
            int temp_num = next_num;
            while (temp_num >= 10) {
                next_num += temp_num % 10;
                temp_num /= 10;
            }
            next_num += temp_num % 10;
            if (next_num <= 10000) {
                numbers[next_num] = true;
            }
        }

        for (int i = 1; i <= 10000; i++) {
            if (!numbers[i]) {
                System.out.println(i);
            }
        }
    }
}

3-2) 풀이 2

위의 코드가 별로 깔끔하지 않아서
다른 분의 코드를 조금 참고해서 수정해보았다.
https://st-lab.tistory.com/53

바뀐 점은,
while 문의 조건을 더 깔끔하게 했다는 점과,,

            while (temp_num != 0) {
                next_num += temp_num % 10;
                temp_num /= 10;
            }

StringBuilder sb = new StringBuilder(); 를 활용해서 더 빠르게 출력할 수 있도록 했다!

public class Main {
    public static void main(String[] args) {
        boolean[] numbers = new boolean[10001];
        for (int i = 1; i <= 10000; i++) {
            int next_num = i;
            int temp_num = next_num;
            while (temp_num != 0) {
                next_num += temp_num % 10;
                temp_num /= 10;
            }
            if (next_num <= 10000) {
                numbers[next_num] = true;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= 10000; i++) {
            if (!numbers[i]) {
                sb.append(i).append("\n");
            }
        }
        System.out.println(sb);
    }
}