[1Day 1Algo] 백준 1065번 한수 (JAVA)

 

N이 1000보다 작다는 조건을 이용하면, if문을 통해 비교적 쉽게 구현할 수 있는 문제이다.

그러나 1000 이상의 숫자도 적용가능한 코드를 작성하고 싶었다.

 

그래서 문자열 인덱싱을 사용하여 코드를 작성하였다.

import java.io.*;

public class Main {
    public static boolean hansu(int n) {
        int prev = n % 10;
        int gongcha = prev - ((n / 10) % 10);

        //      문자열 인덱싱 방식
        String st = Integer.toString(n / 10);
        for (int i = st.length() - 1; i >= 0; i--) {
            int val = (st.charAt(i) - '0');
            if (gongcha != prev - val) return false;
            gongcha = prev - val;
            prev = val;
        }
        return true;
    }

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

        for (int i = 1; i <= n; i++) {
            if(hansu(i)) cnt++;
        }
        System.out.println(cnt);

    }
}

 

코드를 작성하고 보니, '산술연산으로 자릿수를 구분해준다면 더 빠른 프로그램이 되지 않을까?' 라는 생각이 들었다.

 

- String 객체생성 후, Integer.toString 연산 -> 나누기 연산

- charAt() 호출 후, 빼기 연산 -> 모듈러 연산

으로 대체할 수 있기 때문이다.

 

그래서 코드를 조금 변형해 산술연산으로 풀어보았다.

 

import java.io.*;

public class Main {
    public static boolean hansu(int n) {
        int prev = n % 10;
        int gongcha = prev - ((n / 10) % 10);

//        산술연산 방식
        n = n / 10;
        while (n > 0) {
            int val = n % 10;
            if (gongcha != prev - val) return false;
            gongcha = prev - val;
            prev = val;
            n = n / 10;
        }
        return true;
    }

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

        for (int i = 1; i <= n; i++) {
            if(hansu(i)) cnt++;
        }
        System.out.println(cnt);

    }
}

 

산술연산이 훨씬 빠를 것이라는 예상과 다르게 두 방식의 실행시간이 같았다.

Integer.toString()과 charAt()의 성능이 빠르다고 하더라도 이해가 가지 않았다.

 

그래서 n을 100000000으로 놓고 두 방식의 실행시간을 측정하였다.

문자열 인덱싱 방식 / 산술연산 방식

그 결과 1/3 정도 빠른 실행속도를 보여주었다.

 

 

* 추가사항

Integer.toString() 메소드를 사용하는 것보다는String.valueOf() 메소드를 사용하는 것이 더 좋을 것 같다.

그 이유는 null point error(NPE) 때문이다.

변경하고자 하는 object가 null일 경우 toString()은 NPE를 발생시키지만, valueOf()는 null을 반환하기 때문이다.

 

두 함수의 성능차이는 크지 않으므로, 평상시에 NPE를 피할 수 있는 함수를 짜는 것이 추후 유용할 것 같다.