[백준/JAVA] 4673번. 셀프 넘버

이 문제는 사실 시간도 오래 걸리고 어렵게 느껴졌던 문제다,,

단계별로 풀어보기를 순서대로 푸는 중이었는데 갑자기 난이도가 상승한 느낌,,•͈_•͈

 

풀이 1은 내가 구현한 방법이고, 풀이 2는 많은 분들이 boolean 배열을 이용해서 구현한 것을 보고 참고하여 풀어본 것이다.

 

 

알고리즘

 

우선, 문제를 풀기 전에 셀프 넘버 함수 d(n)을 구현하는 방법에 대해서 알아두면 좋을 것 같다.

예를 들어, numSum(123) = 123+1+2+3 = 129 가 저장되게끔 하려면 다음과 같이 구현할 수 있다.

 

1. n이라는 수를 받으면 이를 나중에 리턴 시킬 변수 self에 저장한다. 

static int d(int n) {
		int self = n;
	}

 

2. 각 자릿수의 합을 구하기 위해 n을 10으로 나눈 나머지를 self 변수에 더해 저장해주고, 이후 n은 10으로 나눈 몫을 저장해 한 자릿수를 줄여준다. n을 10으로 나눈 몫이 0이 될 때까지 반복하면 모든 자릿수를 더할 수 있다.

예를 들어, n = 123이라고 한다면,

첫 번째 반복문에서 self에는 123 + (123%10) = 123+3 = 126 이 저장되고,

                         n에는 (123/10) = 12가 저장된다.

두 번째 반복문에서 self에는 126 + (12%1) = 126+2 = 128 이 저장되고,

                         n에는 (12/10) = 1이 저장된다.

세 번째 반복문에서 self에는 128 + (1%10) = 128+1 = 129 가 저장되고,

                         n에는 1/10 = 0 이 저장된다.

while(n>0)의 조건을 만족하지 않으므로 self값을 리턴하고 while문을 빠져나온다.

static int d(int n) {
		int self = n;
		while(n>0) {
			self += n%10; //10으로 나눈 나머지 저장
			n = n/10; //자릿수 줄이기
		}
		return self;
	}

 

 

문제

4673번: 셀프 넘버

 

 

풀이 1

 

함수 d()를 만들고, main에서는 int 배열을 생성하여 d() 함수의 리턴 값을 index로 지정하여 생성자가 존재하는 경우에 해당 index를 count 하는 방법을 이용하였다.

이때, index는 0~9999의 값이지만, i는 1~10000까지이므로 배열에 넣을 때 한 칸씩 당겨서 들어간다는 점을 유의해야 한다. 

public class Main{
    public static void main(String[] args){
        int[] arr = new int[10000]; //생성자 수를 저장할 배열 선언
        for(int i=1; i<=10000; i++) {
        //i를 10000까지 넣으면, d(i)는 10000을 초과하는 경우가 발생하므로 d(i)<=10000 까지만 실행
        	if(d(i)<=10000) {
        		arr[d(i)-1]++; //생성자가 존재하는 경우 count (i는 1~10000이지만, 배열의 index는 0~9999라는 점을 고려하여 1을 꼭 빼줘야함!!)
        	}
        }
        for(int i=0; i<10000; i++) {
        //셀프 넘버=생성자가 존재하지 않는 경우(->해당 index가 count되지 않아 초기값 0이 저장된 경우)
        	if(arr[i]==0){ 
                System.out.println(i+1); //arr[i]에는 i+1의 생성자 수가 저장되어 있으므로 i+1 출력
            }
        }
    }
    
    static int d(int n){
    	int self = n;
    	while(n>0) { //n이 0이 되면 종료
    		self += n%10; //10으로 나눈 나머지 저장
    		n= n/10; //자릿수 하나씩 줄이기
    	}
        return self; 
    }
}

 

 

풀이 2

 

int 배열 대신 boolean 배열을 선언하여 풀어보았다.  그리고 StringBuilder를 이용하여 속도를 높였다.

StringBuilder는 문자열을 이어주는 역할을 하며 객체를 생성하지 않아서 속도가 빠르다.

public class Main {

	public static void main(String[] args) {
		boolean[] arr = new boolean[10000];
		
		for(int i=1; i<=10000; i++) {
			if(d(i)<=10000) {
				arr[d(i)-1] = true;
			}
		}
		
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<10000; i++){
			if(arr[i]!=true) { //false인 인덱스만 출력
				sb.append(i+1).append('\n');
			}
		}
		System.out.println(sb);
	}
	
	public static int d(int n) {
		int self = n;
		
		while(n>0) {
			self += n%10;
			n = n/10;
		}
		return self;
	}

}