[백준알고리즘] 함수 - 4673번 셀프 넘버 문제

알고리즘 공부를 정말 하려고 마음먹고 오랜만에 시도한 문제.

앞까지의 문제들은 다 쉬워보여 이것부터 풀어보고자 첫 문제로 선택했는데,

..문제가 크게 어렵진 않은 것 같아 보였는데 막상 코드로 옮기려고 하니 쉽지 않았다.

뭐든 개념 자체는 간단해보여도 코드로 구현하는것이 어렵구나 느낀다.

학기내내 C++만 쓰다가 간만에 자바로 하려니 헷갈리기도 하다.

냅다 코드를 갈기다가 이런식으로 더 코드를 짜봤자 더 볼것도 없이 시간초과겠구나 싶어 그만두고 더 좋은 코드를 참고하기로 했다.

정말 부끄러울 정도로 비효율적인 (심지어 짜다 만)코드지만, 나는 고작해야 이제 막 공부중인 학생 아니겠는가..

모범답안(?)과 비교하며 셀프 공개처형을 자행하기로 한다..

 

갈기다 만 selfNum 함수 코드는 다음과 같다.

부끄럽지만 3 % 10과같이 연산 결과가 소수로 나오는 경우는 몫과 나머지가 각각 어떻게 구성되는지를 몰랐다.

나는 이 부분을 연산결과가 소수가 나온다면 num이 일의자리수 인 것으로, 그대로 해당 숫자를 저장하고

아니라면 나머지를 저장하는 식으로 배열에 차곡차곡 각 자릿수를 넣어

(지금생각해보면 대체 왜 굳이 배열을 써가며 그랬는지..) d(n)을 구하고자 했다.

그러나 애초에 그럴 필요가 없던 것이었다..자릿수와 상관없이 10으로 나머지 연산을 하면 모든 자릿수들을 구할 수 있다!

(3%10의 몫은 0, 나머지는 3 이런식인 것이었다)

따라서 굳이 일의자리, 십의자리 이상을 if-else문으로 나눠서 다르게 연산할 필요가 없었던것

public static void selfNum(int n) {

        int[] selfNums = new int[10000];    //셀프 넘버를 저장할 배열

        for(int i=0; i<n; i++){     //0~n만큼 돌면서 selfNum인지를 판별할것
            int[] numpos = new int[5];  //10000까지의 selfNum을 구할것이기 때문에 최대 자릿수는 5, 선언과 크기 할당
            for(int j=0; j<i; j++){
                int num = j;
                boolean flag = true;    //자바에서는 boolean이라구 쓴다
                while(flag){   //num이 0보다 작은수가 나온다는건 소수가 나왔다는소리, 즉 1의자리까지 다 계산해봤다는 의미
                    int count = 0;
                    if((num / 10) < 0){ //계산했는데 소수가 나온다면 계산 끝내야함, /은 몫, %은 나머지
                        numpos[count] = num;    //그대로 num을 저장하면 끝
                        count++;
                        flag = false;   //일의자리수까지 확인했으니 while문을 빠져나간다
                    }else{
                        numpos[count] = num % 10;   //나머지를 배열에 저장, 이때 저장되는 순서는 높은 자릿수부터 차례로 저장된다는점!!
                        count++;
                    }
                }
                //구한 numpos배열 바탕으로 0~j까지의 selfNum을 구한다
                int sum = 0;
                for(int k=0; k<numpos.length; k++){    
                    sum += numpos[k];
                }
                if (i == j) {
                    //암튼 이런식으로..반복문이 대체 몇개나 중첩된겨..
                    //j를 i까지 증가시켜가면서 j의 d(n)을 구하고, 그것중에서 i와 일치하는게 있으면 i의 생성자가 있음, 끝내 없다면 생성자가 없는것으로 간주하는 식으로 시도했었다..
                }

            }
        }
    }

이것은 구글링으로 가져온 다른 사람의 코드(원본 출처를 찾지 못함..누군가 알려주신다면 수정해 기입하겠습니다)

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;
	}
}

위의 코드를 보고 참고해서 다시 작성한 코드

 

package Level5;
import java.util.Scanner;

public class SelfNumber {   //백준에 채점할때는 클래스명을 Main으로 해야 컴파일에러가 안생김!

    public static int dNum(int n) {     //n의 d(n)값을 구해 반환하는 함수
        int sum = n;
        while (n > 0){  //n의 일의자릿수까지 계산할때까지 반복
            sum += n % 10;  //n을 10으로 나눈 나머지값은 n의 일의자리 수 값을 의미, 이를 반복하면 처음 n의 모든 자릿수의 값들이 들어가게 되는것
            n = n / 10;
        }
        return sum; //d(n)값 반환
    }

    public static void main(String[] args) {
        boolean[] isNotSelfnum = new boolean[10001];   //bool타입 배열은 false로 초기화된다(지역변수에서는 해당안됨!!) 10000까지를 알아야하므로 크기는 10001로설정
        int result;
        for (int i = 0; i < 10001; i++) {
            result = dNum(i);
//            if (result > 10000) {   //10000까지의 selfnum만 알면 되므로, 초과되면 반복문을 빠져나가도록 한다
//                break;
//이렇게 짜면 안된다. 나는 어떤 n의 d(n)값은 그보다 작은 수의 d(n)값보다 당연히 더 클것이라 가정하고 이렇게 짠건데, 꼭 그렇지 않다!!(189와 200만 생각해봐도)
            if (result < 10001)
                isNotSelfnum[result] = true;    //여기서 true로 저장된다는건 selfnum이 아님을 의미
        }
        for (int i = 0; i < 10001; i++) {
            if(isNotSelfnum[i] == false){   //i번째 배열의 값이 false라면 우리가 알고자 하던 selfNum이라는 소리
                //System.out.println(i + '\n');   //println 자체가 한줄씩 출력되게 하는건데 망각함.이렇게했더니 뒤에 개행문자가 int형변환되어 10씪 더해진 수가 출력되어나왔다;
                System.out.println(i);
            }
        }

    }

}
//일의자리에서 10으로 나눗셈을 하면 나머지와 몫이 어떨게 되어 나오는걸까?소수인데..아!나누어지는 몫이 없으니까 그대로 나머지는 그 수가 되는거구나..
//따라서 굳이 일의자리, 십의자리 이상을 if-else문으로 나눠서 다르게 연산할 필요가 없었던것이다! 코드를 더 간결하게 짤 수 있겠다.
//의식의 흐름대로 막 코드를 작성하다가..이대로면 당연히 시간초과겠구나 싶어 급히 중단하고 다른 코드를 참고하기로 했다. 
//모범 답안을 참고해서 기억나는대로 최대한 안보고 다시 코드를 짰는데, 왜 틀렸다고 나오는지 모르겠다 거의 비슷하게 짠거같은데....
//문제를 보니 예제답안을 보니 9993까지만 출력되어 있는 반면 내 결과는 9995, 9997, 9999까지 출력된다. 이유가 뭘까...
//조건문을 잘못 설정해서 원래 true로 되어있어야 할 자리의 값들이 그대로 false로 되어있어서 그렇게 된거였다!!

참고를 해서 다시 모범답안 코드를 보지 않고 최대한 혼자 힘으로 다시 코드를 작성했는데

처음에는 컴파일 에러, 그다음은 틀렸습니다로 나왔다.

컴파일 에러는 괄호를 하나 빠뜨려서, 클래스명을 Main으로 안바꿔서였던건데

틀렸습니다는 왜 나왔는지 의문이었다. 방식이 틀린건 아닌것같은데 뭐가 잘못된건지 또 골똘히 생각해보았다..

문제는 조건문을 잘못 설정해서였다.

값이 10000을 초과해서 나오는 순간부터는 그 다음 수들도 초과될것이라 생각해서 반복문을 빠져나가도록 한게 잘못이었다.

주석에도 적어놓았지만 생각해보니 그렇지 않았다. 

따라서 원래 true로 되어있어야 할 자리의 값들이 그대로 false로 되어있어서, 후반부의 값들이 잘못 더 출력되어 나왔던것이다!

 

 

 

이 문제를 풀어보며 얻어가게 된 점들을 정리해보자.

- 한 값을 10으로 계속 나누어가며 나머지들을 구하면 곧 그 값의 자릿수들이 구해지게 된다.(일의자리->십의자리..순으로)
- 컴파일 에러가 난다면 괄호를 빠뜨린게 있는건 아닌지, 백준상에서 클래스명이 Main으로 잘 되어있는지 확인
- selfnumber인지 10000까지를 알고 싶은 것이므로 배열의 크기를 적어도 10001로 해야한다. (크기를 10000으로 해놓으면 0~9999니까)
- 조건문 설정할때는 조건이 옳은지, 이게 최선인지 의심하기!!

 

그리고 나는 익숙한 println을 사용하여 출력했는데, 참고한 코드를 보니 stringBuilder를 이용했다.

입출력을 최대한 가볍게 하면 더 빠르게 컴파일이 될 것 같으나, 아직 버퍼 등 다른 방식의 원리를 모르기도 하고 익숙하지 않다.

다음번에는 bufferedReader, stringBuilder 등을 공부해서 더 빠르게 입출력을 할 수 있도록 하는 것으로 하자.