[BaekJoon/백준] 7단계 "함수"

이에 해당하는 문제는 15596번, 4673번, 1065번이다. 이 글에서는 4673번과 1065번만 다루도록 하겠다.

 

∙ 4673번

해당 문제를 풀면서, 정말 많은 생각을 했다. 문제 페이지를 열자마자 내가 제일 싫어하는 수학적 글들이 보임과 동시에 한숨부터 쉬었지만, 열심히 풀어보려고 노력했다. 어쩌면 내가 해당 문제를 너무 과대평가하는 바람에 시간을 많이 소모한 것 같다. 이 문제의 풀이 방식은, 문제에서 주어진 가장 큰 숫자까지 셀프 넘버가 아닌 숫자들을 먼저 모두 구한뒤에, 그에 해당하지 않는 숫자들인 셀프넘버들을 그냥 출력해주면 된다. 이렇게 되면 총 2만번 정도의 시간복잡도가 계산되는데, 주어진 시간은 1초밖에 주어지지 않아서 나는 이 방법은 당연히 아니겠거니 하고 다른 규칙이나 방법을 찾아보려고만 노력했다. 물론 그렇게 생각했더니 답이 안나왔다. 생각하면 할수록 모든 경우의 수를 다 구해서 경우의 수가 아닌 것들을 구해야 하는, 내가 처음 생각했던 방식으로 해야할 것만 같았다. 근데 주어진 시간은 1초..프로그램의 실행 속도에 대한 개념이 별로 없기 때문에 나는 당연히 이게 불가능할거라고 생각했지만 혹시나 하는 마음에 해봤다. 해당하는 방식대로 해본 결과 프로그램의 실행 속도는 겨우 0.11초. 내가 컴퓨터를 무시해도 많이 무시했나보다. 컴퓨터는 생각보다 빠른 녀석이었다. 문제를 풀고 다른 분들은 어떻게 구현하셨나 하고 찾아봤더니 다 방법은 똑같았다. 다들 2만번의 작업을 수행했다. 다만 내 코드는 불필요한 코드들이 너무 많았다. 부끄럽지만 코딩 초보인 나와 다른사람들의 코딩 실력을 날것 그대로 비교해보겠다.

 

아래는 지저분한 나의 코드이다. (이것을 참고하지 마시오!!)

import java.util.ArrayList;
import java.util.Arrays;

public class main {
    public static void main(String args[]) {
        ArrayList<Integer> intz = new ArrayList<Integer>();
        for(int i=1;i<10001;i++)
        {
            int r = d(i);
            if(!intz.contains(r))
                intz.add(r);
        }
        int[] arr = intz.stream().mapToInt(i->i).toArray();
        Arrays.sort(arr);

        int counter=0;
        for(int i = 1; i <10001;i++)
        {
            if(i<arr[counter])
                System.out.println(i);
            else
                counter++;
        }
    }

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

제출한 코드는 위와 같으나, 지금 봐도 지우거나 간결하게 수정하고 싶은 부분들이 너무 많다. d 함수에 대해서는 간결하게 잘 짰다고 생각하나, 문제를 쉽게 풀진 못했기 때문에 메인함수 부분에 여러번 고민, 수정한 흔적과 그로 인해 불필요한 과정들이 눈에 많이 보인다.

 

아래는 다른 고수분의 코드다.

public class Main {
    static boolean[] num = new boolean[10001];
    public static void main(String[] args) {
        for(int i = 0; i < 10000; i++) {
            int idx = selfNum(i);
            if(idx <= 10000) { // 이런식으로 10000을 넘기는 불필요한 값들은 필터링함.
                num[idx] = true; // 이런식으로 하면서 아예 중복검사를 필요치않게만듦.
            }
        }
        for(int i = 0; i < 10000; i++) {
            if(!num[i]) {
                System.out.println(i);
            }
        }
    }

    public static int selfNum(int n) {
        int sum = n;
        while(true) {
            if(n == 0) {
                break;
            }
            sum += n%10;
            n = n/10;
        }
        return sum;
    }
}

메인함수 부분의 구현에 엄청난 차이가 느껴진다. 주석처리한 부분은 내가 캐치하지 못한 아주 기발한 방법이다.

i를 0부터 9999까지 셀프넘버 함수에 넣어주면서, 만약 결과가 10000 미만일 경우에만 배열에 true 값을 저장해 주는 방식이다.

나의 경우는 쓸데없이 배열을 두 번이나 만들고, 소트하고 중복값을 검사해주고, 그리고 함수의 결과값으로 10000이 넘어도 저장되는 방식이였는데, 이분은 나의 모든 쓸데없는 경우를 다 제외해버리셨다. 정말 놀라웠다.

 

그래서 마음을 다잡고 다시 내 코드를 간결하게 짜봤다. (나의 코드 최종본)

import java.util.ArrayList;
import java.util.Arrays;

public class Main {
    public static void main(String args[]) {
        int number[] = new int[10001];

        for(int i = 1; i<10001; i++) {
            int key = d(i);
            if(key<=10000)
                number[key]++;
        }
        for(int i = 1; i<10000; i++) {
            if(number[i]==0)
                System.out.println(i);
        }
    }

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

 

 

∙ 1065번

해당 문제는 간단하나, 내가 야매를 썼기에 자백하는 마음에 글을 작성하려고 한다. 사실 이 문제를 열었을 때에도 '한수' 라는 처음 듣는 수학 단어가 나왔고 일반사람보다 수학적 사고방식이 부족한 탓에 문제를 이해하는 데에도 시간이 좀 걸렸다 ㅎㅎ.. 사실 문제 이해는 못했고, 밑에 나온 출력 결과로 이해할 수 있었다. 한수는 각 자리 수가 등차수열인 수를 말하는데, 그렇다면 한자리수부터 두자리수까지는 무조건 각 자리가 등차수열인 수가 되고, 세자리수부터만 다루면 된다. 문제에서 제공하는 입력값은 1000이하의 자연수인데, 1000은 등차수열 아니길래 그냥 코드에서 제외하고 세자리 수만 다뤘다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static void main(String args[])
    {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        try{
            int N = Integer.parseInt(br.readLine());
            int count = 0;
            for(int i=1;i<=N;i++) {
                if(is_hansu(i))
                    count++;
            }
            bw.write(""+count);
            bw.flush();
            br.close();
            bw.close();
        }catch (Exception e){

        }
    }

    public static boolean is_hansu(int n)
    {
        if(n<100)
            return true;
        else if(n==1000)
            return false;
        else
        {
            int z[] = new int[3];
            for(int i=0;i<3;i++) {
                z[i]=n%10; n/=10;
            }
            int gap = z[1]-z[0];
            return (gap==(z[2]-z[1])) ? true : false;
        }
    }
}

그래서인지 is_hansu 함수가 조금 쪽팔리긴 하다.. 반성하는 의미로 글을 쓰는 거니 다음부터는 이런 조잡한 기술은 쓰지 않도록 노력할 것이다. 일관성 있는 코드를 위해서!