[BOJ - JAVA] 백준 1105번: 팔

Problem

https://www.acmicpc.net/problem/1105

1105번: 팔

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

Input

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

 

Output

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

---

문제 해결 과정

특별한 알고리즘이 생각이 나지 않아 일단 예시를 들며 문제를 접근하였다.

  Case 1 -  L, R의 자리 수가 다른 경우

 

    Case 1의 예시로 주어진 L, R을 생각해보자.

   L: 823부터 R: 8812 까지 사이의 수 중 900 1000 등 8의 개수가 0인 수가 존재하게 된다.

 

    만약 이 두 수의 사이의 간격이 넓어서 이러한 수가 있다고 생각한다면 다른 예시를 보자.

   L: 8, R: 11 인 경우에도 9, 10, 11 등 8의 개수가 0인 수가 존재하게 된다.

    따라서 L, R의 자리 수가 다른 경우에는 답은 0이 된다. 

 

  Case 2, 3 -  L, R의 자리 수가 같은 경우

 

    Case 2의 예시로 주어진 L, R을 생각해보자.

   L: 2314부터 R: 3241 까지 사이의 수에는 L, R 자신을 포함하여 8의 개수가 0인 수가 존재하므로 이러한 경우도 답이 0이 나온다.

 

    하지만 만약 Case 3의 경우 처럼 L 또는 R에 8이 포함되어 있는 경우 최소 개수가 0이 아닐 수 있다.

   Case 3의 경우 처럼 L: 8808, R: 8880인 경우 앞의 두 자리인 88이 겹치게 되므로 최소 2개의 8을 갖게 된다.

   그러므로 자리 수가 같은 경우 두 수를 가장 큰 자리 수부터 비교를 하며 같은 자리에 있는 수가 달라질 때까지 8의 개수를 조사하면 된다.

   따라서 L, R의 자리 수가 같은 경우에는 가장 큰 자리 수부터 같은 자리에 있는 수가 달라질 때까지 존재하는 8의 개수가 답이 된다. 

---

My Solution Code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ1105 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        String L = st.nextToken();
        String R = st.nextToken();

        int answer = 0;

        // 자리 수가 다른 경우 답은 0이다.
        if(L.length() != R.length()){
            System.out.println(answer);
        }
        // 자리 수가 같은 경우 각 맨 앞자리 수 부터 비교하며 8의 개수를 센다.
        else {
            int i = 0;
            while( i < L.length() && L.charAt(i) == R.charAt(i)) {
               if(L.charAt(i)  == '8') {
                   answer++;
               }
               i++;
            }
            System.out.println(answer);
        }
    }
}