[백준 4673번] 셀프넘버 with Java

guswls·2024년 4월 21일

구현 백준

알고리즘

목록 보기

1/39

문제

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

코드

import java.util.*;

class Main {
	public static void main(String[] args) {
		boolean[] check = new boolean[10001];

		for (int i = 1; i < 10001; i++) {
			// 1. i + (i의 각 자리수 합 )구하기
			int notSelf = i;
			String[] str = String.valueOf(i).split("");
			for (int j = 0; j < str.length; j++) {
				notSelf += Integer.valueOf(str[j]);
			}

			if (notSelf > 10000) {
				continue;
			}

			// 2. self가 아닌 인덱스를 true로 변경
			check[notSelf] = true;
		}

		//3. self가 아닌 수를 출력
		StringBuilder sb = new StringBuilder();
		for (int i = 1; i < 10001; i++) {
			if (!check[i]) {
				sb.append(i).append(System.lineSeparator());
			}
		}

		System.out.println(sb);
	}
}

문제 이해

문제를 오해하지 않도록 조심해야된다. 셀프넘버는 d(n)은 만족하는 수가 아니라 만족하지 않는 수를 의미한다.
문제에서 제시된 d(n)은 자기 자신 + 각 자리수의 합을 의미한다.
따라서 d(n)으로 생성되지 않는 10000 이하의 수를 구하면 된다.

풀이 방법

주석에 적힌 단계를 따라가며 문제를 해결하면 된다.
d(n)으로 생성될 수 있는 모든 경우를 구해야되기 때문에, check라는 boolean배열로 판단한다.

구체적인 단계는 다음을 따른다.

먼저 첫번쨰 for문을 돌며 i에 대한 d(n)을 구한다

check 배열에 그 수에 해당하는 인덱스의 값을 true로 변경한다.

위 1, 2번을 i <= 10000일 때 까지 수행한다.

위 for문에서 갱신된 check배열을 순회하며 값이 false인 인덱스만 StringBuilder에 담은 후 출력한다. 그 값이 곧 문제의 셀프넘버를 의미한다.

핵심 포인트

문제를 이해할 떄 조심하여야 한다. 단순히 d(n)에서 구해진 수를 다시 d(n)에 넣어서, 즉 d(d(n)), d(d(d(n))), ....의 조건에 해당하는 수만 구하는 것이 아닌 1이상 10,000이하의 수에서 모든 d(n)을 구할 수 있는 경우를 구해야 한다.
문제 아이디어는 어려운 것이 없고 문제 요구대로 풀면 쉽게 풀리는 문제이나, 각 자리수의 합을 구하는 로직이 곧바로 안떠오를 수 있다.

보완할 점 / 느낀 점

이전에 한번 풀어봤던 문제라 시행착오 없이 쉽게 풀 수 있었으나, 각 자리수의 합을 구하는 로직이 바로 떠오르지 않았다.
일단은 찾아보고 풀고싶지 않아 떠오르는대로, 위와 같이 String으로 형변환해서 각 자리수를 구하고, 그것을 다시 int로 형변환해서 각 자리수의 합을 구하는 방법으로 해결했었다.
하지만 실행시간과 메모리가 둘 다 이전의 풀이보다 두 배 이상 걸렸다.
(아마도 String으로 형변환하는 과정에서 많은 메모리가 소비되는 것으로 보인다)
자리수의 합을 구하는 로직 정도는 암기해놓아야 이런 문제를 풀 때 바로바로 적용할 수 있을 것 같다.

참고자료

1. 개선된 코드

import java.util.*;

class Main {
	public static void main(String[] args) {
		boolean[] check = new boolean[10001];

		for (int i = 1; i < 10001; i++) {
			// 1. i + (i의 각 자리수 합 )구하기
			int notSelf = getNotSelf(i);
			if (notSelf > 10000) {
				continue;
			}

			// 2. self가 아닌 인덱스를 true로 변경
			check[notSelf] = true;
		}

		// 3. self가 아닌 수를 출력
		StringBuilder sb = new StringBuilder();
		for (int i = 1; i < 10001; i++) {
			if (!check[i]) {
				sb.append(i).append(System.lineSeparator());
			}
		}

		System.out.println(sb);
	}

	static int getNotSelf(int num) {
		int ret = num;

		while (num > 0) {
			ret += num % 10;
			num = num / 10;
		}

		return ret;
	}
}