SWEA 14450. 정수 입력기

구간 [L, R] 이 주어지고 Q개의 정수가 주어질 때, 숫자가 구간 안에 포함되는지 확인하는 문제이다.

 

숫자가 구간 안에 들어온다는 것은 구간 안의 어떤 숫자의 접두사가 될 수 있다는 것이다. 즉, 입력된 숫자를 low,와 high로 나눈 후,  끝에 0과 9를 계속 붙여서 확장하면서 R보다 작거나 같으면서 숫자가 구간 안에 들어가는지 확인해야 한다. R보다 커질 때 까지 못 찾으면 불가능한 숫자이다.

private static boolean isValidPrefix(long L, long R, long n) {
    long currentLow = n;
    long currentHigh = n;
    while (currentLow <= R) {
        if (Math.min(currentHigh, R) >= Math.max(currentLow, L)) {
            return true;
        }
        currentLow *= 10;
        currentHigh = currentHigh * 10 + 9;
        if (currentLow > R) break;
    }

    return false;
}

 

 

결과 코드는 다음과 같다.

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

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        for (int tc = 1; tc <= T; tc++) {
            sb.append('#').append(tc).append(' ');
            StringTokenizer st = new StringTokenizer(br.readLine());
            long l = Long.parseLong(st.nextToken()), r = Long.parseLong(st.nextToken());
            int q = Integer.parseInt(st.nextToken());
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < q; i++) {
                long n = Long.parseLong(st.nextToken());
                if (isValidPrefix(l, r, n)) {
                    sb.append('O');
                } else {
                    sb.append('X');
                }
            }
            sb.append('\n');
        }
        
        br.close();
        System.out.print(sb);
    }
    
    private static boolean isValidPrefix(long L, long R, long n) {
        long currentLow = n;
        long currentHigh = n;
        while (currentLow <= R) {
            if (Math.min(currentHigh, R) >= Math.max(currentLow, L)) {
                return true;
            }
            currentLow *= 10;
            currentHigh = currentHigh * 10 + 9;
            if (currentLow > R) break;
        }

        return false;
    }
}