[백준알고리즘/함수] 4673번 문제 : 셀프 넘버(자바/JAVA)

안녕하세요

백준 알고리즘 단계별로 풀어보기 6단계 함수의 셀프 넘버를 풀어봤습니다

이번 문제는 지금까지 단계별로 풀어보기를 제가 풀면서 제일 어려웠던 문제였습니다

갑자기 난이도 확 상승한 느낌;;

난이도 올라가서 그런지 처음 풀었을 때 풀긴풀었지만 소스 코드도 마음에 안 들고 다른 사람들과 속도를 비교했을 때 속도차이도 많이나서 아쉬웠습니다 ㅠㅜ

계속해서 최적화를 해서 결국에는 어느정도 속도가 비슷하게 구현을 했습니다

제가 풀은 방식 2가지, 그리고 다른 분이 구현한 알고리즘을 참고하여 구현한 1가지 방식에 대해서 설명하겠습니다

 

---

문제 링크

www.acmicpc.net/problem/4673

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보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 증가하는 순서로 출력한다.

 

 

---

 

 

문제 풀이

제일 먼저 저 혼자 풀어서 제출한 방식입니다

만약 정답을 알기위해 제 블로그를 오셨다면... 이 방법은 참고가 많이 안 될 것 같습니다 ㅠ

while문을 사용하여 풀은 방식입니다

풀다보니 함수도 안 쓰고 그냥 풀었네요

함수로 풀어야할 부분을 이중while문을 사용해서 계산해서 풀었습니다

public class Main {
	public static void main(String[] args) {
		int[] SelfNumber = new int[10001];	// 셀프넘버를 넣을 배열 선언
		int count = 1;						// count 변수 -> 1씩 증가
		int Self = 0;						// 셀프넘버를 계산해 넣을 변수 선언
		int i = 0;							// 셀프넘버 계산을 위한 변수 선언

		// count가 10000보다 작을 때까지 반복
		while (count < 10000) {
			// 처음 시작은 count로 초기화
			Self = count;
			i = count;

			// 0이 될때까지 반복
			while (i != 0) {
				// i를 10으로 나눈 나머지를 계속 더해서 계산
				Self += i % 10;
				i /= 10;
			}

			// 10000보다 작은 것만 배열에 입력
			if (Self < 10000)
				SelfNumber[Self]++;

			// count증가
			count++;
		}

		// 10000보다 작은 셀프넘버를 출력
		for (int j = 1; j <= 9999; j++) {
			if (SelfNumber[j] == 0) {
				System.out.println(j);
			}
		}
	}
}

 

---

두 번째 방식입니다

처음보다는 나아졌지만 역시 마음에 들지 않네요

보다시피 셀프넘버를 구하는 부분을 함수로 만들어서 풀었습니다

하지만 함수를 두 번 호출하여 쓸데없이 연산을 더 하게 구현을 했습니다

이것도 마음에 안드네... ㅠ

public class Main {
	public static void main(String[] args) {		
		int[] SelfNumber = new int[10001];	// 셀프넘버를 넣을 배열 선언
		int count = 1;						// 초기 count 선언

		// 반복문 시작
		while (count < 10000) {
			// 10000보다 작은 셀프넘버가 아닌 값을 배열에 입력
			if (Self(count) < 10000)
				SelfNumber[Self(count)]++;

			count++;
		}

		// 10000보다 작은 셀프넘버를 출력
		for (int j = 1; j <= 9999; j++) {
			if (SelfNumber[j] == 0) {
				System.out.println(j);
			}
		}
	}
	
	// 셀프넘버를 구하는 메소드 선언
	public static int Self(int n)
	{
		// 초기값 세팅
		int total = n;
		
		// 반복문을 사용 10으로 나눈 나머지를 계속해서 더해서 계산
		while(n != 0) {
			total += n % 10;
			n /= 10;
		}
		
		// 결과 return
		return total;
	}
}

 

---

마지막 방법입니다

다른 분이 풀었던 방법을 참고하여 풀었습니다

참고 소스

www.acmicpc.net/source/25469924

 

위의 1, 2번 방식과 많이 차이가 납니다...

일단 while문이 아닌 for문을 바탕으로 풀고

int[] 배열에서 boolean[] 배열을 사용햇습니다

왜 처음 할 때는 boolean[] 배열을 생각하지 못 했지... ㅠㅜ

System.out.print도 stringBuilder를 사용하여 한 번만 호출합니다

마지막 방법이 메모리측면, 시간측면에서 훨씬 최적화되도록 구현했네요

여기까지 제가 풀은 세 가지 방법이었습니다

public class Main2 {
	public static void main(String[] args) {
		// 셀프넘버를 넣을 배열 선언
		boolean check[] = new boolean[10001];

		// 1-10000까지 반복 -> 셀프넘버가 아닌 경우 배열에 true로 입력
		for (int i = 1; i < 10001; i++) {
			int n = Self(i);
			if(n<10001)
				check[n] = true;
		}
		
		// StringBuilder 선언
		StringBuilder sb = new StringBuilder();
		
		// 반복문을 사용 false인 경우 셀프넘버
		for(int i=1;i<10001;i++) {
			if(check[i]!=true)
				sb.append(i).append('\n');
		}
		
		// 결과 출력
		System.out.print(sb);
	}

	// 셀프넘버를 구하는 메소드 선언
	public static int Self(int n) {
		int total = n;
		while (n != 0) {
			total += (n % 10);
			n /= 10;
		}
		return total;
	}
}

 

---

속도 비교

1번 : while문 + 함수 사용x

2번 : while문 + 함수 사용

3번 : for문 + 함수 사용

 

차례대로 속도를 비교한 이미지입니다

역시 마지막에 풀었던 방식이 압도적으로 빠른 것을 볼 수 있습니다

이상 백준 알고리즘 4673번 셀프 넘버를 풀은 내용이었습니다!

 

다음 문제 : 2021.05.10 - [알고리즘/알고리즘JAVA] - [백준알고리즘/함수] 1065번 문제 : 한수(자바/JAVA)

이전 문제 : 2021.05.08 - [알고리즘/알고리즘JAVA] - [백준알고리즘/함수] 15596번 문제 : 정수 N개의 합(자바/JAVA)