백준 1105번: 팔

문제

L과 R이 주어진다. 이때, L보다 크거나 같고, R보다 작거나 같은 자연수 중에 8이 가장 적게 들어있는 수에 들어있는 8의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 L과 R이 주어진다. L은 2,000,000,000보다 작거나 같은 자연수이고, R은 L보다 크거나 같고, 2,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 L보다 크거나 같고, R보다 작거나 같은 자연수 중에 8이 가장 적게 들어있는 수에 들어있는 8의 개수를 구하는 프로그램을 작성하시오.

나의 풀이

• 문제를 보자마자 생각난건 완전탐색이 였으나 범위가 너무 커 시간초과 예상

• 다른 방법을 고민하던 중, 자릿수와 각 자리의 숫자에서 규칙 발견

  • L과 R의 자릿수가 다르면 → 최소 8의 개수는 0

  • L과 R의 자릿수가 같으면 → 앞에서부터 숫자가 다를 때까지는 동일한 숫자가 유지됨

나의코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        
        String L = s[0];
        String R = s[1];
        
        int cnt = 0;
        
        if (L.length() == R.length()) {
            for (int i = 0; i < L.length(); i++) {
                if (L.charAt(i) != R.charAt(i)) break;
                if (L.charAt(i) == '8') cnt++;
            }
        }
        
        System.out.println(cnt);

    }
}

시간 복잡도

• L과 R이 같고 10자리 수(최대 2,000,000,000) 일경우 -> O(L.length()) -> O(10)

결론적으로 시간 복잡도는 O(1)