[백준 알고리즘 문제풀이][JAVA][4673번] 셀프 넘버

문제 - 백준 문제 바로가기

셀프 넘버는 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보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 출력하는 프로그램을 작성하시오.

입력

입력 없음.

출력

10,000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 증가하는 순서로 출력한다.

시간제한

1초

알고리즘 유형

수학
사칙연산

에라토스테네스의 체 - 위키백과 내용 참조.

2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
자기 자신을 제외한 2의 배수를 모두 지운다.
남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
자기 자신을 제외한 3의 배수를 모두 지운다.
남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
자기 자신을 제외한 5의 배수를 모두 지운다.
남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
자기 자신을 제외한 7의 배수를 모두 지운다.
위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

그림의 경우, 11² > 120 이므로 11보다 작은 수의 배수들만 지워도 충분하다.
즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.

예제입력 1

예제출력 1

1
3
5
7
9
20
31
42
53
64
 |
 |       <-- a lot more numbers
 |
9903
9914
9925
9927
9938
9949
9960
9971
9982
9993
  

풀이 1

import java.io.*;
import java.util.HashSet;
import java.util.Set;

public class No4673_셀프넘버 {

  public static void main(String[] args) throws IOException {
    try{
      go();
    }catch(IOException e){e.printStackTrace();}
  }

  private static void go() throws IOException{
    BufferedWriter bw = new BufferedWriter( new OutputStreamWriter( System.out ) );
    int x = 10000;
    int idx=0;
    int[] xar = new int[x];
    for(int i=1; i<=x; i++){
      //들어온숫자로 만들수 있는 IDX 가져오기
      idx = next(i);
      if(idx-1<x) xar[idx-1] = 1;
    }
    for(int i=0; i<xar.length; i++){
      if(xar[i] < 1) bw.write((i+1)+"\n");    //셀프넘버 출력
    }
    bw.flush();
  }

  private static int next(int a){
    int res=0;
    String[] arr = String.valueOf(a).split("");
    for(String x:arr) res+=Integer.parseInt(x);
    res+=a;
    return res;
  }

}

풀이 2

import java.io.*;
import java.util.HashSet;
import java.util.Set;

public class No4673_셀프넘버 {

  public static void main(String[] args) throws IOException {
    go2();
  }

  private static void go2() {

    Set<Integer> set = new HashSet<Integer>();
    for (int x=1; x<=10000; x++) set.add(x);
    int newNumber;
    String arr[];
    for (int x=1; x<=10000; x++){
      newNumber = x;
      arr = (x+"").split("");
      for(int y=0; y<arr.length; y++) newNumber += Integer.parseInt(arr[y]);
      //if(newNumber > 10000) break;
      set.remove(newNumber);
    }
    for(int i: set) System.out.println(i);
  }

}

GitHub 소스는 아래에서 확인 가능합니다.

[풀이]

Baekjoon Algorithm solve JAVA No.4673 셀프 넘버

이전[백준 알고리즘 문제풀이][JAVA][4344번] 평균은 넘겠지

다음[백준 알고리즘 문제풀이][JAVA][5622번] 다이얼