백준 문제 풀이 - 브루트 포스 단계 - 2213번 분해합 (브론즈 2)

이번 단계는 브루트 포스 단계이다. 먼저 브루트 포스란 말 자체를 처음 듣는지라 브루트 포스 알고리즘이 뭔지는 알아보고 문제를 시작하기로 하였다.

 

브루트 포스(Brute Force) - 완전 탐색

브르투 포스란 직역하면 짐승같은 힘, 무식한 힘이라는 뜻이다.

설명 그대로 무식하게 처음부터 끝까지 모든 경우를 다 탐색하는 알고리즘으로 완전 탐색의 종류 중 하나이다.

 

즉, 모든 경우를 고려한 방법으로 확실한 정답을 찾을 수 있는 장점이 있지만, 그만큼 모든 경우의 수를 다 고려하기 때문에 실행시간이 오래 걸리는 편이다.

 

방법은 조건문을 이용하여 모든 경우의 수를 찾는 것으로 모든 경우의 수를 반복하며 조건을 이용하여 정답을 찾아낸다.

 

 

자 그렇다면 문제로 다시 돌아와 보자, 우리는 어떤 수 N이 들어왔을때 자기 자신과 자기의 각 자리수를 더한 값이 N인 생성자 M 중에서 가장 낮은 값을 찾으려고 한다.

입력받은 값은 최대 100만으로 자리 값을 알 수 없으므로 나는 입력받은 String을 charArray로 변환한 후 2중 for문을 통하여 N부터 0까지의 값을 검증하고자 하였다.

코드를 살펴보면 다음과 같다.

 

import java.io.*;

class Main{
    public static int n,min,temp;
    public static String s;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        br.close();
        min = 9999999;

        for(int i = n; i > 0; i--){
            s = Integer.toString(i);
            temp = i;
            for(char c : s.toCharArray()){
                temp += Integer.parseInt(String.valueOf(c));
            }
            if(temp == n && i<min){
                min=i;
            }
        }

        if (min == 9999999) {
            System.out.println(0);
        } else {
            System.out.println(min);
        }
    }
}

min 값은 입력의 최대치가 100만이므로 임시로 9,999,999라는 값을 주었다.

그리고 for문을 이용하여 n부터 1까지 반복하며 각 자리수의 합이 입력받은 값과 일치하고 현재 min 값보다 적은 경우 min값으로 설정되게 하여 가장 작은 값을 가져올 수 있었다.

 

결과적으로 코드는 정상적으로 작동하였는데 효율성면에서 살펴보니 484ms로 시간이 꽤 걸리는 편이었다.

다른 사람들과 비교했을때에 높은 수준은 아니였지만 그렇다고 낮은 수준도 아니였으므로 조금더 효율적으로 구현한 사람들의 코드를 찾아보았는데, 개인적으로 가장 좋았다고 생각하는 코드는 다음과 같다.

 

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

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int answer =0;
		
		for(int i=0; i<N; i++) {
			int number =i;
			int sum =i;
			
			while(number !=0) {
				sum += number%10;
				number /=10;
			}
			
			if(sum == N) {
				answer = i;
				break;
			}
		}
		System.out.println(answer);
	}

}

보면 정말 코드가 심플한데, 일단 0부터 N 까지 반복하며 현재값 i를 10으로 나눈 나머지를 Sum에 더한다.

그리고 number를 10으로 나눠주고 sum이 n과 같은 경우 break하여 반복문을 탈출한다.

 

이렇게 되면 예를 들어 i가 216인 경우 216 % 10이 되므로 첫번째 반복에서는 sum에 6이 들어가게 된다.

그리고 10을 나누면 타입이 int이기 때문에 소수점은 버려지고 21만 남게된다.

2번째 반복에서는 1이 sum에 더해지고 10을 나눠 2만 남게될 것이다.

 

또한, 어차피 가장 낮은 값을 구하는것이 목적이기에 0부터 시작해서 올라가고 처음 값이 나오면 바로 break를 걸면 됬었는데 이걸 미처 생각하지 못했던게 많이 아쉽다.

실제로 내 코드를 0부터 시작하도록 바꾸어 보았는데,

 

for(int i = 0; i < n; i++){
            s = Integer.toString(i);
            temp = i;
            for(char c : s.toCharArray()){
                temp += Integer.parseInt(String.valueOf(c));
            }
            if(temp == n && i<min){
                min=i;
                break;
            }
        }

크게 차이는 안나지만 40ms 정도가 줄어드는 것을 확인 할 수 있었다.

아마 내 코드에서는 형변환과 배열 반환시에 시간이 좀 소모되는 것이 아닌가 추정해 본다.