1105 팔

자바 / 실버 1 / 그리디 알고리즘

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

 

알고리즘을 생각하고 나서는 쉽게 구현할 수 있었다. 그런데 생각을 좀 얕게 했던 탓인지... 여러 반례가 많이 발견되어 3트 정도 했다.

 

주요 코드는 다음과 같다.

if (L.length() == R.length()){
            for(int i = 0; i < L.length(); i++){
                if (L.charAt(i) == R.charAt(i)){
                    if (L.charAt(i) == '8')
                        num++;
                }
                else
                    break;
            }
        }

 

알고리즘

자릿수가 다르다면, 답은 무조건 0이므로 비교할 필요가 없다.

자릿수가 같다면, 각 수의 맨 앞자리부터 같은 지를 비교하며 8의 개수를 센다.

같지 않은 자리가 등장는 순간 반복문을 종료한다.

 

 

구글링을 통해 참고했던 여러 반례들

8181 8282 -> 답: 1

1280 1281 -> 답: 1

883812 883803 -> 답: 3

8880 8890 -> 답: 3

 

 

다음은 전체 코드이다.

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

public class Main{
    private static String L, R;
    private static int num = 0;

    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
    
        StringTokenizer st = new StringTokenizer(s);
        L = st.nextToken();
        R = st.nextToken();
        
        if (L.length() == R.length()){
            for(int i = 0; i < L.length(); i++){
                if (L.charAt(i) == R.charAt(i)){
                    if (L.charAt(i) == '8')
                        num++;
                }
                else
                    break;
            }
        }
        System.out.println(num);
    }
}