[백준] 3165번. 5(JAVA)

문제

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

---

풀이(45분)

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

public class Main {

    private static final char FIVE = '5';
    private static StringBuilder number;
    private static int targetCount;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long initialNumber = Long.parseLong(st.nextToken()) + 1;
        number = new StringBuilder(String.valueOf(initialNumber)).reverse();
        targetCount = Integer.parseInt(st.nextToken());

        backtrack(0, false);
        countAndAppendFives();
        System.out.println(number.reverse().toString());
    }

    private static void backtrack(int idx, boolean shouldRoundUp) {
        if (idx >= number.length() || countFives() >= targetCount) {
            return;
        }

        if (shouldRoundUp) {
            number.setCharAt(idx - 1, FIVE);
        }

        if (countFives() >= targetCount) {
            return;
        }

        char currentChar = number.charAt(idx);
        if (currentChar < FIVE) {
            number.setCharAt(idx, FIVE);
            backtrack(idx + 1, false);
        } else if (currentChar > FIVE) {
            number.setCharAt(idx, '0');
            long addValue = 1;
            for (int i = 0; i <= idx; i++) {
                addValue *= 10;
            }
            long num = Long.parseLong(number.reverse().toString()) + addValue;
            number = new StringBuilder(String.valueOf(num)).reverse();
            backtrack(idx + 1, true);
        } else {
            backtrack(idx + 1, false);
        }
    }

    private static int countFives() {
        int count = 0;
        for (int i = 0; i < number.length(); i++) {
            if (number.charAt(i) == FIVE) {
                count++;
            }
        }
        return count;
    }

    private static void countAndAppendFives() {
        int currentCount = countFives();
        while (currentCount < targetCount) {
            number.append(FIVE);
            currentCount++;
        }
    }
}

---

문제 풀이 전략

 

😭 정확한 케이스를 생각하지 않고 문제에 냅다 뛰어들어 시간을 엄청 소비한 문제였다.

✅ 조건이 단순하더라도 다양한 케이스와 경우를 생각하고 문제에 들어가자.

 

💡케이스 정리

1. 입력 : 99 1 -> 출력 : 105

간단한 경우다.

1의 자리에서 5를 기준으로 (미만, 5, 이상)을 생각해야 한다는 아이디어를 얻을 수 있다.

 

2. 입력 : 595 2 -> 출력 : 655 

1번과 동일하다. 해당 자리에서 5를 기준으로 생각하면 된다.

 

3. 입력 : 6 1 -> 출력 : 15

자릿수를 올리며 해결해 주면 된다

 

4. 입력 : 46 1 -> 출력 : 50

자릿수를 올리며 바로 5를 넣어주는 게 아니라 올려준 자릿수가 5가 되었는지를 검사해야 한다는 아이디어를 얻어야 한다.

 

5. 입력 : 56 1 -> 출력 : 57

자릿수를 굳이 올릴 필요 없이 이미 해결되었다.

 

6. 입력 : 56 2 -> 출력 : 155

자릿수가 앞까지 올라갔다.

---

이를 메서드에 넣고 정리해 주면 된다.

 

메서드에 넣고 정리하는 것은 그렇게 어렵지 않은데 조건을 하나하나 분석하며 정확한 분기를 작성하는 게 어려웠다.

 

꼭!! 조건을 먼저 생각하자.