15949. 현석이의 생일

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;


public class Solution {
    public static void main(String[] args) throws Exception {
        new Solution();
    }

    private final Boolean USE_FILE_INPUT = false;

    private BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    private BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

    private Solution() throws IOException {
        if (USE_FILE_INPUT) {
            useFileIO();
        }
        solve();
        close();
    }

    private void useFileIO() throws IOException {
        System.out.println("[Warn] You are using file input stream.");
        close();
        try {
            bufferedReader = new BufferedReader(new InputStreamReader(new FileInputStream("./test_input.txt")));
            bufferedWriter = new BufferedWriter(new OutputStreamWriter(new FileOutputStream("./test_output.txt")));
        } catch (FileNotFoundException e) {
            throw new IllegalArgumentException("File Not Found.");
        }
    }

    private void close() throws IOException {
        bufferedReader.close();
        bufferedWriter.close();
    }

    private void solve() throws IOException {
        int T = Integer.parseInt(bufferedReader.readLine());
        for (Integer testCaseNo = 1; testCaseNo <= T; testCaseNo++) {
            bufferedWriter.write("#"+testCaseNo+" "+solveTestcase()+"\n");
        }
    }

    private final String CASE_IMPOSSIBLE = "-1";

    private String solveTestcase() throws IOException {
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        String N = stringTokenizer.nextToken();
        // x와 y는 0~9 사이의 범위이므로 단일 문자로 볼 수 있다. (항상 y > x 이다.)
        Character x = stringTokenizer.nextToken().charAt(0);
        Character y = stringTokenizer.nextToken().charAt(0);
        return solveTestcase(N, y, x);
    }

    /**
     * 쟁점: N은 최악의 경우 10^100000 이기 때문에 String 형태를 유지한 채로 연산하는 것이 포인트라고 생각한다.
     * digit단위로만 처리하면 되어서 BigInteger로 치환하는 과정이 반드시 필요한 것은 아니므로 String 형식을 유지하며 답을 구하는 것이 가능하다.
     * @param answer
     * @return
     */
    private String solveTestcase(String targetNumberDigits, Character bigComponentDigit, Character smallComponentDigit) {
        StringBuilder answerStringBuilder = new StringBuilder();
        Character targetDigit;
        Boolean isMSB;
        Boolean hasCarry = false;
        for (int i = 0; i < targetNumberDigits.length(); i++) {
            targetDigit = targetNumberDigits.charAt(i);
            isMSB = i == 0;
            if (hasCarry || targetDigit >= bigComponentDigit) {
                answerStringBuilder.append(bigComponentDigit);
                hasCarry |= targetDigit > bigComponentDigit;
                continue;
            }
            if (isMSB && smallComponentDigit == '0') {
                hasCarry = true;
                continue;
            }
            if (targetDigit >= smallComponentDigit) {
                answerStringBuilder.append(smallComponentDigit);
                hasCarry |= targetDigit > smallComponentDigit;
                continue;
            }
            if (isMSB) {
                hasCarry = true;
                continue;
            }
            // 앞자리 수로 돌아가서 캐리를 만들어와야하는 경우.
            while (true) {
                i--;
                // 더 이상 앞에서 캐리를 가져올 수 없는 경우.
                if (i < 0) {
                    return CASE_IMPOSSIBLE;
                }
                // 앞자리에서 캐리를 만들어오는 과정
                Character removedDigit = answerStringBuilder.charAt(i);
                answerStringBuilder.deleteCharAt(i);
                // 큰 수를 작은 수로 다운그레이드
                if (removedDigit == bigComponentDigit) {
                    answerStringBuilder.append(smallComponentDigit);
                    break;
                }
                // ...혹은, 가장 첫 숫자가 작은 수면 이를 제거하는 대신 다음 자릿수에서 캐리로 사용 가능
                if (i == 0 && removedDigit == smallComponentDigit) {
                    break;
                }
                // 그 외에는 더 앞자리 수에서 가져오는 방법 밖에 없음.
            };
            hasCarry = true;
        }
        String answer = answerStringBuilder.toString();
        if (isValidAnswer(answer)) {
            return answer;
        }
        return CASE_IMPOSSIBLE;
    }

    private Boolean isValidAnswer(String x) {
        return !x.isEmpty();
    }
}