[BOJ] 4673번 셀프 넘버

문제

www.acmicpc.net/problem/4673

4673번: 셀프 넘버

풀이

1) 처음 풀이 (메모리 : 296772, 시간 : 920ms)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
	
	static boolean isSelfNum(int num) {
		for(int i=1;i<num;i++) {
			String tmp = i+"";
			int len = tmp.length();
			int sum=i;
			for(int j=0;j<len;j++)
				sum+=(tmp.charAt(j)-'0');
			if(sum==num)
				return false;
		}
		return true;
	}
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		for(int i=1;i<=10000;i++) {
			if(isSelfNum(i))
				sb.append(i+"\n");
		}
		System.out.println(sb);
	}
}

 

제발 모든 문제를 Bruteforce 로 풀려고 하는 습관을 버렸으면 좋겠다. 솔직히 기업 코딩 테스트 문제에 브루트포스로 풀 문제는 거의 잘 안나올 것 같다. 제발 더 효율적인 방법을 찾을 수 있도록 더 고민해보고 브루트포스를 시도해보자...

 

2) 개선 코드( 메모리 : 14840, 시간 : 160ms)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {

	static int get_next(int num) {
		int sum = num;
		while(num/10!=0) {
			sum+=num%10;
			num/=10;
		}
		sum+=num;
		return sum;
	}
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		boolean[] chk = new boolean[10001];
		for(int i=1;i<=10000;i++) {
			int tmp = get_next(i);
			if(tmp<10001)
				chk[tmp] = true;	
		}
			
		for(int i=1;i<=10000;i++) {
			if(!chk[i])
				sb.append(i+"\n");
		}
		System.out.println(sb);
	}
}