[백준/Java] 25709번 1빼기

문제

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

민겸이는 1 빼기를 할 수 있는 능력을 가지고 있다. 1 빼기란, 다음의 두 연산 중 하나를 골라 수행하는 것이다.

1. 가지고 있는 수에서 1을 뺀다.
2. 가지고 있는 수에 있는 1을 하나 지운다. 지우고 난 뒤 좌우의 수들을 순서대로 다시 합쳐 하나의 수로 만든다. 이때 맨 앞의 연속되는 0은 지워진다.

민겸이가 최초로 가지고 있는 정수가 하나 주어질 때, 이 수를 0으로 만들기 위해 최소 몇 번의 1 빼기가 필요한지 구해보자.

입력

민겸이가 가지고 있는 정수 N이 주어진다.

출력

민겸이가 해당 수를 0으로 만들기 위해서 최소 몇 번의 1 빼기가 필요한지 출력한다.

---

문제 이해

민겸이는 두 가지 방법으로 숫자를 줄일 수 있다.

1. 현재 숫자에서 1을 뺀다
2. 숫자 안에 있는 ‘1’을 하나 지운다.
3. 지운 뒤 남은 숫자들은 이어 붙이고, 맨 앞의 연속된 0은 모두 제거

민겸이가 가진 숫자 N이 주어질 때,

이 숫자를 0으로 만들기 위한 최소 연산 횟수를 구하는 문제

---

문제풀이 방법

• N이 0이 될 때까지 반복
• 현재 숫자에 '1'이 포함되어 있으면 → '1' 하나 제거
• 그렇지 않으면 → N = N - 1
• 연산 횟수를 1 증가
• N = 0이 되면 연산 횟수를 출력

---

나의 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int count = 0;

        while (N != 0) {
            String strN = String.valueOf(N); // 문자열로 변환
            if (strN.contains("1")) { // 1 포함시
                // '1'을 하나 제거
                int index = strN.indexOf('1'); // 가장 맨 앞의 1의 위치를 찾음
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < strN.length(); i++) {
                    if (i != index) sb.append(strN.charAt(i)); // 해당 위치 문자열을 빼고 붙임
                }
                String resultStr = sb.toString().replaceFirst("^0+", ""); // 앞쪽 0 제거
                N = resultStr.isEmpty() ? 0 : Integer.parseInt(resultStr);
            } else {
                N--; // '1'이 없으면 -1
            }
            count++;
        }

        System.out.println(count);
    }
}

---

코드 설명

Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int count = 0;

• 사용자로부터 N을 입력 받음
• 연산 횟수를 카운트하기 위해 count를 0으로 초기화

String strN = String.valueOf(N);
if (strN.contains("1")) {

• 현재 숫자 N을 문자열로 바꿔서 1이 포함되어 있는지 확인
• 1이 있으면 1 제거 , 없으면 -1

int index = strN.indexOf('1');
StringBuilder sb = new StringBuilder();
for (int i = 0; i < strN.length(); i++) {
    if (i != index) sb.append(strN.charAt(i));
}

• 가장 앞쪽의 1 위치인 index를 첮음
• 그 위치의 문자를 제외하고 나머지 문자들은 StringBuilder로 다시 이어붙임 → 1을 하나 지운 숫자가 완성됨
  

String resultStr = sb.toString().replaceFirst("^0+", "");

• 어떻게 0으로 시작하면 지우지 고민하다가 정규표현식을 사용해도 된다는 걸 보고…
• 정규표현식 사용
• ^0+ → 문자열 처음부터 연속된 0 제거
• StringBuilder 객체인 sb를 toString()으로 문자열로 바꿈

N = resultStr.isEmpty() ? 0 : Integer.parseInt(resultStr);

• 만약 모든 숫자가 지워져서 빈 문자열이면 N = 0
• 아니면 문자열을 숫자로 변환해서 N에 저장

else {
    N--;
}

• '1'이 아예 없으면 -1 연산만 가능
• N--으로 1을 빼줌