본문 바로가기

별걸다하는 IT/알고리즘 문제풀이

[백준 Baekjoon 알고리즘] 4673번 셀프 넘버 문제 및 풀이, 오답 풀이

[백준 Baekjoon Algorithm]

[4673] 셀프 넘버 self number?

 

문제

셀프 넘버는 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,6,75,86,97

10000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 출력하는 프로그램을 작성하시오.

 

입출력 input output

입력은 없다.

출력

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

예제출력

음..표로 직접 작성하려다가 너무 긴거같아서 사진으로 대체..ㅎㅎㅎ

문제를 읽고 풀어보세요~!

해설은 밑으로 스크롤~~

ANSWER

오늘 드디어 '함수 사용하기' 단계로 넘어왔네요~! 이 문제는넥슨에서 가장 쉬운 난이도로 기출된 문제라고 합니다. 문제가 넘나 기네요..ㅎㅎ 이런거는 예시를 보는게 훨 이해가 빠르죠 ㅎㅎ

생성자가 없는 숫자가 셀프 넘버래요 1은 1+1=2가 되고 0은 0+0이 되므로 1은 생성자가 없는 셀프넘버가 되는거죠 ㅎㅎ

일단 생각나는 방법은 10000 공간을 잡아놓고 셀프넘버가 아닌 것들을 지워서 셀프넘버만 남기는 방법이네요.

13이 13+3+1 = 17을 만들고 이 17이 다시 17+1+7 =25의 생성자가 되는 뭔가 릴레이되죠?

그 전께 다시 생성자가 되니까 재귀로 풀 수도 있겠어요. 하지만 재귀 문법은 왠만하면 지양하는게 좋은거 알고 계시죠?!

또 반복문을 돌면서 그 수가 셀프넘버인지 아닌지 판별하고 그 때 그 때 출력해줄 수 있는 방법이 있을 수 있겠네요.

ㅎㅎ 일단 문제를 풀어봅시다. 함수 단계인만큼 함수를 정의해서 풀어줄게요

 

d(n)함수 정의

[C++ d(n)함수 정의하기]

먼저 d(n) 함수를 작성해봅시다.

int d(int n) {
    return n + (n/1000) + (n%1000)/100 + (n%100)/10 + (n%10);
}

이렇게 작성할 수도 있겠지만 이거는 이 문제에서만 사용할 수 있는 함수겠죠? N이 100이 되버리면 해당 N의 크기에 맞게 변경해줘야 해요.

int d(int n) {
	int num = n;
	do {
		num += n % 10;
	} while ((n /= 10) != 0);
	return num; 
}

고래서 저는 요렇게 작성해줬답니다. ㅎㅎ 이렇게 하면 N이 100이어도 로직이 바뀌지 않아도 되겠죠?

 

그 외 d(n)을 아래처럼 풀어낸 풀이도 찾아볼 수 가 있었습니다.

 

[자바 d(n)함수 정의하기]

위의 C++이랑 똑같이 함수를 JAVA를 정의해준 모습입니다. 조금의 차이(?)를 주기 위해 C언어에서는 do~while문을 Java에서는 일반 while문을 사용해봤어요.

public static int d(int n) {
       int num = n;
       while(n != 0) {
           num += n % 10;
           n /= 10;
       }
       return num;
}

이제 main함수를 작성해줄게요

 

먼저 배열을 모두 1로 초기화해준다음에 셀프넘버가 아닌 것만 지워나갈수도 있고 (이럴 경우 배열은 셀프넘버 모임이 되겠죠?)

배열을 0으로 초기화해준다음에 셀프넘버가 아닌것들을 1로 올릴 수 있어요 이럴 경우 배열은 셀프넘버가 아닌 수들을 갖는 모임이 될거예요. 둘다 시작이 0이냐 1이냐 차이일뿐이지 똑같아요 

문제에서는 셀프넘버를 물어봤으니까 배열을 셀프넘버를 찾는 용이라 생각하고 1로 초기화해볼게요

 

초기화

[4673번 C++ 초기화 부문]

먼저 10000이런거 쓰다가 자칫 0헷갈려서 실수나기 쉽잖아요? 실수를 줄여주기 위해 얘를 상수로 정의하거나 #를 써서 매크로정의를 해줍시다.

#define MAX 10001 //매크로 사용

문제 조건을 보면 셀프 넘버가 10000보다 작거나 같을 수 있어요

즉 0~ 10000이 되므로 총 10001을 잡아줬습니다.

const int MAX = 10001; //상수 사용

그 다음 1의 원소를 가지는 배열을 초기화시켜줄게요. 나중에 '1이면 셀프넘버가 맞다, 0이면 셀프넘버가 아니다'를 판별하는 용도로 쓰일거예요

bool selfAry[MAX];
fill_n(selfAry, sizeof(selfAry), true);

보통 많이 실수하는 부문 중에 하나가 

bool selfAry[MAX] = {true};

이렇게 초기화해줬을 때 입니다. 이럴 경우 첫 인덱스에만 true가 저장이 되고 나머지는 자동으로 0으로 초기화 돼버려요 ㅎㅎ 조심해줍시다. 아직 문제해결이 안되신분들은 한 번 배열을 넉넉히 출력해서 초기화가 제대로 들어갔는지 확인해보는 것은 어떤가요?ㅎㅎ

 

아니면 배열 말구 간편하게 vector를 써서 assign으로 한번에 초기화시켜주는 것도 좋은 방법입니다.

vector<bool> selfAry;
selfAry.assign(MAX, true);

 

[4673번 JAVA 초기화 부문]

자바의 경우 Arrays.fill()메서드를 이용해서 한 번에 초기화해주면 됩니다. import java.util.Arrays; 이렇게 라이브러리 앞에 추가해주는거 잊지말규!

private static final int MAX = 10001;
    public static void main(String[] args) {
    	boolean[] selfAry = new boolean[MAX];
    	Arrays.fill(selfAry, true);	
    }

 

전체 코드

[JAVA - 셀프넘버인지 판별하는 배열을 통해 풀기]

import java.util.Arrays;
public class Main {
    public static final int MAX = 10001;
    public static int notSelfNum;
    public static void main(String[] args) {
        boolean[] selfAry = new boolean[MAX];
        Arrays.fill(selfAry, true);
        for (int i = 1; i < MAX; ++i) {
            notSelfNum =d(i);
            if (notSelfNum < MAX) {
                selfAry[notSelfNum] = false;             
            }
        }  
        for (int i = 1; i < selfAry.length; ++i) {
            if (selfAry[i]) {
                System.out.println(i);              
            }
        }
    }
    private static int d(int n) {
        int dn = n;
        while(n > 0) {
            dn += n % 10;
            n /= 10;
        }
        return dn;
    }
}

[C++ 셀프넘버인지 판별하는 배열을 통해 풀기]

#include <iostream>
#include <vector>
#define MAX 10001
using namespace std;
int d(int);
int main()
{
	vector<bool> selfAry;
    selfAry.assign(MAX, true);
    int notSelfNum;
	for (int i = 0; i < MAX; i++) {
		notSelfNum = d(i);
	    if(notSelfNum>MAX)
            continue;
		selfAry[notSelfNum] = false;
	}
	for (int i = 0; i < MAX; i++) {
		if (selfAry[i]) {
			cout << i << endl;
		}
	}
	return 0;
}
int d(int n) {
	int num = n;
	do {
		num += n % 10;
	} while ((n /= 10) != 0);
	return num; //생성차로 추출된 d(n)
}

제거 풀다가 실수한 것 중에 continue;를 break;로 넣어버려서 틀렸더라고요 ㅎㅎㅎ

break를 사용하면 반복문을 빠져나와버리기 때문에 continue로 그 뒤의 수까지 계속 탐방(?)해줘야합니다. ㅎㅎ 넘나어이없는 실슈 ㅠㅠ

 

[재귀를 이용해서 풀기 C++]

이번에는 재귀를 이용해서 풀어줬습니다.

#include<iostream>
#define MAX 10001
using namespace std;
int d(int, bool*);
int main() {
	bool selfAry[MAX]; int notSelfNum;
	fill_n(selfAry, sizeof(selfAry), true); //일단 모두 셀프넘버로 초기화

	for (int i = 1; i < MAX; i++) {
		if (selfAry[i] == false)
			continue;
		d(i, selfAry);
	}
	for (int i = 1; i < MAX; i++) {
		if (selfAry[i]) {
			cout << i << "\n";
		}
	}
	return 0;
}
int d(int n, bool arr[]) {
	int num = n;
	do {
		num += n % 10;
	} while ((n /= 10) != 0);
	if (num >= MAX) return 0;
	if (arr[num] == true) {
		arr[num] = false;
	}
	return d(num, arr);
}

 

[그때그때 판별하는 방법으로 풀기 C++]

이번에는 그 때 그 때 생성자를 판별해줍시다.

19가 셀프넘버가 아니고 , 20이 셀프넘버라는 것을 어떻게 알 수 있을까요?

만약 num이 두 자리 수라면, num + num%10 + num/10 = 19인 num이 존재하면 19는 셀프넘버가 아니겠죠. 그리고 존재하지 않으면 셀프넘버일거예요. 즉 범위탐색이 되겠네요.

탐색의 범위를 줄이기 위해 여기에 적용할 수 있는 조건을 생각해볼까요? num은 무조건 19보다 작아요.num이 19가 되버리면 일단 19를 더하고 시작하니, 해당 값보다 커질수밖에 없겠죠?

#include<iostream>
using namespace std;
int d(int);
int main() {
	int n = 1;
	int i,maxPlace;
	//자리수 판별을 위한 배열
	int place[5] = { 1, 10, 100, 1000, 10000 }; 
	while (n <= 10000) {
		//n의 자리수 찾기.
		for (i = sizeof(place)-1 ; i >= 0; i--)
			if (n / place[i] != 0) {
				break;
			}
		maxPlace = i; //if maxPlace =0, it has one digit.
		int constructorN = 0;   //생성자 개수
		for (i = 0; i < n; i++) { 
			if (d(i) == n)
				constructorN += 1;
		}
		if (constructorN == 0) cout << n << '\n';
		n++;
	}
	return 0;
}
int d(int n) {
	int num = n;
	for (int i = n; i > 0; i /= 10) {
		num += i % 10;
	}
	return num;
}

메모리: 1988KB

시간: 260ms

코드길이: 558B

이렇게 해줬더니 정답은 떴는데 시간을 초큼 더 잡아먹네요. 범위가 그렇게 크지 않아서 서칭을 그냥 0부터 시작해줬는데 num이 커질수록 비효율적일 것 같긴해요. 일단 얘도 고쳐보고, 또 sizeof함수를 가독성 때문에 써줬는데 얘때문에 시간을 잡아먹는거 같기도 하고 ㅎㅎ 한 번 다시 수정해볼까요.

 

규칙을 찾아봅시다

num이 8473이면 num의 생성자를 찾기 위해서 탐색을 시작할 n은1000자리수의 값이 영향을 많이 미칠거예요.

5999인 경우 5999+27+5로 고작 6000대밖에 안되니까요. 이 숫자에 영향을 미친것은 5999가 가장 크고 나머지는거의 영향을 개 쪼금 미쳤어요ㅎㅎ 왜냐 나머지 숫자들은 아무리 더해봤쟈 9+9+9+... = 1000을 넘기가 힘들기 때문입니다.

따라서 탐색 범위를, 8473일 경우 8+9+9+9인 35를 빼면 8402가 남습니다. 그럼 이 수부터 탐색을 하면 되겠죠? 즉 탐색 범위는 (앞자리 숫자 + 남은 digit개수*9)를 n에서 빼준 값부터 시작하면 될 것 같네요.

 

전체 코드

이렇게 바꿔줬습니다. ㅎㅎ

#include<iostream>
using namespace std;
int d(int);
int main() {
	int n = 1;
	int i,maxPlace;
	int place[5] = { 1, 10, 100, 1000, 10000 }; 
	while (n <= 10000) {
		for (i = 4 ; i >= 0; i--)
			if (n / place[i] != 0) {
				break;
			}
		maxPlace = i; 
		int constructorN = 0;  
		for (i = n -(n/place[maxPlace] + maxPlace*9); i < n; i++) {
			if (d(i) == n)
				constructorN += 1;
		}
		if (constructorN == 0) cout << n << '\n';
		n++;
	}
	return 0;
}
int d(int n) {
	int num = n;
	for (int i = n; i > 0; i /= 10) {
		num += i % 10;
	}
	return num;
}

메모리: 1988KB

시간: 0ms

짠! ㅎㅎ 총 세가지 방법으로 풀어봤어요.

정성이 가득들어갔는데이 ♥도움됐다면 공감&댓글&광고보답은 우떤가요?! ㅎㅎ