[백준] 1105_팔 / 그리디

 

 

Sliver

 

문제

 

L과 R이 주어진다.

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

 

 

입력

 

첫째 줄에 L과 R이 주어진다.

L은 2,000,000,000보다 작거나 같은 자연수이고,

R은 L보다 크거나 같고, 2,000,000,000보다 작거나 같은 자연수이다.

 

 

출력

 

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

 

 

---

 

 

풀이

 

import java.util.*;
import java.io.*;

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

        // 1. L과 R의 길이가 다르면 8이 겹칠 가능성이 없음 -> 0 리턴
        if(L.length() != R.length()){
            System.out.println(0);
            return;
        }

        int count = 0;
        // 2. 같은 자리수를 갖는 경우, 앞자리부터 비교
        for(int i=0; i<L.length(); i++){
            if(L.charAt(i) != R.charAt(i)) 
                break; // 숫자가 달라지면 이후는 무의미하므로 중단
            if(L.charAt(i) == '8') 
                count += 1; // 같은 숫자면서 8이면 카운트 증가
        }

        System.out.println(count);
    }
}

 

해결방법

 

• L과 R을 입력받는다.
• L과 R의 길이가 다르면 8이 겹치지 않을 수 있으므로 바로 0을 출력한다. 
• L과 R의 길이가 같다면, 왼쪽부터 한 자리씩 비교한다.
  - L과 R의 현재 위치의 숫자가 같다면 비교를 계속하고, 두 숫자가 다르다면 더이상 8이 겹치지 않을 수 있으므로 탐색을 종료한다.
  - 두 숫자가 같으면서 8 이라면 카운트를 증가시킨다. 

 

 

그리디 (Greedy)

• 가능한 한 앞자리에서부터 최대한 '8'을 찾으려 한다.
• 한번 숫자가 달라지는 순간 이후로는 더 이상 '8'이 연속으로 나올 가능성이 없으므로 즉시 중단한다.

 

 

 

---

 

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