Algorithm

[Java] 백준 4673 - 셀프 넘버

isaac.kim 2022. 4. 25. 22:16
728x90
반응형

[Java] 백준 4673 - 셀프 넘버

백준 사이트에서 '문제-단계별 풀어보기'를 쭉 풀어보던 중 함수 파트에서 이 문제를 만났다.

 

백준 4673 - 셀프 넘버

입력

없음

 

출력

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

 

 

예제 출력은 다음과 같다. 중간에 <-- a lot more numbers는 출력하는 것이 아니고 중간 생략...

 

 

코드 풀이

일단 문제를 봤을 때는 재귀 함수를 써야 될 것 같았지만 여기서는 반복문을 사용한다.

 

먼저 셀프 넘버인지 아닌지를 체크하는 함수가 필요하다. 

 

문제에서 말하는 생성자가 있는 수는 셀프 넘버가 아니다. 셀프 넘버가 아닌 수를 구하는 식이 주어졌으므로 참고해서 셀프 넘버가 아닌 수를 골라낸다.

 

셀프 넘버가 아닌 수는, 자신과 자신의 구성 숫자들을 1의 자리로 만들어 모두 더한 값이 된다.

 

public static int getNotSelfNumber(int i) {
    int sum = i;

    while ( i != 0) {
        sum = sum + (i % 10);
        i = i / 10;
    }

    return sum;
}

셀프 넘버가 아닌 수를 구하는 로직을 보자.

 

1234 이라는 숫자를 넣었을 때 반환되는 수는 1234 + 4 + 3 + 2 + 1 연산의 값이어야 한다.

 

1234를 10으로 나머지 연산을 하면 1의 자리를 구할 수 있다. 1234 % 10 = 4

다음 1234를 10으로 나눈 값은 123이 되는데 여기서 위와 같이 1의 자리를 구한다.

123을 10으로 나머지 연산을 하면 1의 자리를 구할 수 있다. 123 % 10 = 3

다음 123을 10으로 나눈 값은 12가 되는데 여기서 위와 같이 1의 자리를 구할 수 있다.

12를 10으로 나머지 연산을 하면 1의 자리를 구할 수 있다. 12 % 10 = 2

다음 12을 10으로 나눈 값은 1가 되는데 여기서 위와 같이 1의 자리를 구할 수 있다.

1을 10으로 나머지 연산을 하면 1의 자리를 구할 수 있다. 1 % 10 = 1

다음 1을 10으로 나눈 값은 0된다. (정수형 계산)

 

입력값 1234에서 반환된 값은 1244인데 이 값은 생성자들이 있엇으므로 셀프 넘버가 아니다.

 

입력된 수와 각 자리 숫자들을 구하여 모두 더한 값이 Self Number가 아닌 수가 된다.

 

 

다른 예)

 

1이 들어오면

sum = 1

 

1 != 0 이므로 반복문 실행

sum = 1 + (1 % 10);

i = 1 / 10; // 0

이므로 반복문이 종료된다.

 

최종 연산된 sum은 2가 되어 반환되고, 이 값은 셀프 넘버가 아닌 값이 된다.

 

 

 

 

 

여기서 반환된 숫자는 셀프 넘버가 아니라고 할 수 있다. 셀프 넘버가 아닌 것을 체크하기 위해 boolean 배열을 생성하고, 반환값을 갖는 인덱스에 표시한다. 

boolean[] noneSelf = new boolean[10001];

// 1부터 10000까지의 셀프 넘버를 찾자.
for (int i = 1; i <= 10000; i++) {
    int n = getNotSelfNumber(i);

    if (n <= 10000) noneSelf[n] = true;
}

범위 10000보다 작은 값의 boolean 배열 인덱스의 값을 true로 세팅한다.

true이면 셀프 넘버가 아닌 숫자이다.

 

// false인 self인덱스만 출력
for(int j = 1; j <= 10000; j++ )
    if (!noneSelf[j]) System.out.println(j);

boolean 배열에 셀프 넘버인 인덱스의 값은 false이기 때문에 false 값을 확인해서 출력한다. (범위 10000까지)

 

 

 

전체 소스코드

public class Main {
	public static void main(String[] args) {
		
		boolean[] noneSelf = new boolean[10001];
		
		// 1부터 10000까지의 셀프 넘버를 찾자.
		for (int i = 1; i <= 10000; i++) {
			int n = getNotSelfNumber(i);
			
			if (n <= 10000) noneSelf[n] = true;
		}
		// false인 self인덱스만 출력
		for(int j = 1; j <= 10000; j++ )
			if (!noneSelf[j]) System.out.println(j);
	}

	public static int getNotSelfNumber(int i) {
		int sum = i;
		
		while ( i != 0) {
			sum = sum + (i % 10);
			i = i / 10;
		}
		
		return sum;
	}
}

 

 


다음에는 재귀 함수를 사용해서 풀어봐야겠다.

728x90
반응형