h.o.Algorithm | Java | 백준 28135 - Since 1973 - 숫자열 포함을 어떻게 확인할 것인가

백준 28135 문제를 통해 숫자열 포함 처리 방법을 생각해보는 글이다.

h.o.Algorithm - Java 백준 28135

h.o.Algorithm - String - 숫자열 포함 어떻게 확인할까

문제

어떤 수에 50이 들어가면 그 수를 한 번 더 세기로 하였다. 예를 들어, 5152는 한 번만 세지만 5050이나 5051은 한 번 더 센다.
이 방식대로 1부터 차례대로 수를 셀 경우 N이 몇 번째에 처음으로 등장하는지 구하여라.

입력

$$ N이 주어진다.  (1<=N<=1,000,000) $$

동기

항상 이와 같은 문제를 만나면, 가장 단순한 방식으로 확인해 정답을 확인하고 넘어가거나 효율적인 코드만 찾다가 풀지도 못하고 시간만 너무 많이 허비하곤 했다. 이번엔 일단 단순한 방식으로 풀어 보고 조금씩 효율적인 방식을 찾는 방식으로 리팩토링을 해보고자 이 글을 작성한다.

풀이

문자열 포함여부 확인

머릿속에 있는 가장 간단한 해결 방식은 String클래스의 contains() 메서드를 사용하는 것이다.

• 시간 복잡도 O(N) : contains()를 사용하더라도 시간 복잡도는 O(N)이며 최댓값이 백만(1,000,000)이므로 큰 문제가 없다고 판단했다.

import java.io.*;

public class baekjoon28135 {
    static final String FIFTY = "50";

    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++){
            String comparand = String.valueOf(i);
            cnt++;
            if(i==N){
                System.out.println(cnt);
                return;
            }
            if(comparand.contains(FIFTY)){
                cnt++;
            }
        }
    }
}

• 장점 : 구현이 간단하다. (코드가 짧다.)
• 단점 : 하지만 숫자를 매번 String으로 변한하고, 문자열 하나하나를 비교하는 contains() 메서드를 사용하는 건 비효율적이다. (contains()때문에 시간복잡도는 실은 $$ O(Nlog(N)) $$였던 것 같다.

결과는 성공이지만, 좀 더 효율적으로 코드를 작성할 수 없는지 고민해 본다.

수학적 접근

모든 수에서 50을 포함하고 있는지 확인하는 별도 메서드를 활용해 볼 수 있을 것 같다.

import java.io.*;

public class baekjoon28135 {
    static final int FIFTY = 50;

    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++){
            cnt++;
            if(i==N){
                System.out.println(cnt);
                return;
            }
            if(containsFifty(i)){
                cnt++;
            }
        }
    }

    private static boolean containsFifty(int n){
        int num = n;
        while(num>=10){
            int comparand = num%100;
            if(comparand == FIFTY){
                return true;
            }
            num /= 10;
        }
        return false;
    }
}

• 시간복잡도 O(Nlog(N) : N번의 연산을 하지만, 숫자의 자릿수 -1 만큼 (2자리 이상일 경우) 연산이 늘어나므로 O(NlogN)을 갖는다.
• 장점 : 수를 문자열로 변환하는 과정이 없어지는데, 문자열 메모리를 N의 수만큼 할당했던 지난 코드에 비해서 공간복잡도가 줄어들었다.
• 결과

문자열로 처리할 때보다 메모리는 약 80%, 시간은 50% 이상 절약할 수 있었다.

정리

• 해당 문제에서 첫번째와 두번째 풀이에서 가장 큰 차이는 수를 문자열로 변환해서 처리했는지 여부이다. String 클래스와 contains()와 직접 구현한 containsFifty()의 연산의 수 자체는 큰차이가 없어 보이지만, CPU 관점에서 원시타입(primitive)인 정수를 비교하는 것과 참조타입(reference)인 문자열을 비교하는데에서 많은 차이를 보인다. 해당 문제에서는 문자열의 길이가 2인 50이었기 때문에 '큰'차이가 없고 문제를 통과할 수 있었지만 문자열의 길이가 늘어나면 늘어날수록 비교 연산에 사용되는 CPU 리소스가 증가하게 된다. 따라서 수를 이용해 비교할 수 있다면 수를 사용하는 것이 좋다.
• 코드길이가 다가 아니다. 두번째 풀이의 코드가 첫번째 코드보다 코드길이는 60%정도 길다. 하지만 전체적인 성능에선 2배 이상의 성능을 보인다. 코드가 짧고 가독성이 좋다고 무조건 좋은 코드라고 할 수 없는 것이 이런 사례들 때문인 것 같다.