크-게 만들기

크게 만들기

 

백준 2812번 문제

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

2812번: 크게 만들기

 

 

 

1. 문제

 

 

 

2. 풀이 방법

2.1 내림차수 만들기

2.1.1 개념

주어진 숫자에서 K개를 지웠을 때 가장 큰 수가 되게 하려면 숫자의 앞자리(왼쪽)가 가장 커질 수 있는 방향으로 수를 지우면 될 것이다.

즉 특정 자릿수를 지워 숫자를 내림차순이 되는 형태로 만들면 가장 큰 수가 될 수 있다.

 

숫자를 내림차수로 만드는 데에는 스택을 활용할 수 있다.

 

다음과 같이 예시가 주어졌다고 하자

 

10자리,

지울 수의 개수  = 4,

숫자 = 4177252841

 

[내림차순 예_그 1]

 

스택을 사용해서 숫자를 내림차순으로 만드는 방법은 다음과 같다.

 

1. 왼쪽부터 숫자를 탐색한다.

2. 스택에서 꺼낸 값보다 탐색한 숫자가 크다면 스택에 있는 숫자를 빼고 제거한다(스택이 비어있으면 넘어간다).

3. 조건이 충족하는 한 2를 반복한다.

4. 탐색한 숫자를 스택에 넣는다.

 

위 방식을 이용하면 오름차순인 경우의 숫자가 다 제거되기 때문에 내림차순 형태의 숫자가 된다.

 

 

[내림차순 예_그 2]

 

두 번째 자리까지 탐색했을 때 스택에 가장 위에 있는 수보다 큰 수가 없었기 때문에 탐색한 값이 그대로 스택에 들어가게 된다.

 

 

[내림차순 예_그 3]

 

세 번째 자리를 탐색했을 때 4, 1 < 7 이므로 스택에 있는 4와 1을 차례대로 제거하고 세번째 자릿수인 7로 스택에 넣어준다.

 

 

[내림차순 예_그 4]

 

다섯 번째 자리를 탐색했을 때 스택상황은 위와 같아진다.

 

 

[내림차순 예_그 5]

 

여섯 번째 자리를 탐색했을 때 2 < 5 이므로 스택에서 2를 제거하고 5를 넣어준다.

 

 

[내림차순 예_그 6]

 

앞의 방식대로 숫자를 탐색하면 여덟 번째 자리를 탐색할 때 스택의 가장 위에 있는 수 2(일곱 번째 자릿수)를 제거하게 된다.

그리고 숫자를 삭제할 수 있는 개수는 4개까지이므로 탐색을 종료한다.

 

최종적으로 스택을 활용해서 775841이라는 값을 만들었다.

이 값은 완전한 내림차순은 아니지만 4개의 숫자를 제거했을 때 적어도 왼쪽부터 내림차수가 되도록 만들어진 수이기 때문에 가장 큰 값이 된다.

 

 

2.1.2 코드

[Number]

public static class Number {
    int number;
    boolean deleted = false;

    public Number(int number) {
        this.number = number;
    }
 }

 

자릿수에 대한 정보를 갖고 있는 Number라는 클래스를 만들었다.

deleted는 해당 자릿수가 제거됐는지를 나타낸다(true => 제거됨).

 

 

[deleteLeftSideNumber]

public static int deleteLeftSideNumber(Number[] numberArr, int count) {

    Stack<Number> stack = new Stack<>();

    for (Number number : numberArr) {
    //스택이 비어있거나, 스택에서 꺼낸 값이 탐색한 값보다 작을 경우 스택에 있는 값을 제거
        while (!stack.isEmpty() && stack.peek().number < number.number) {
            count--;
            Number deletedNumber = stack.pop();
            //스택에서 꺼낸 값을 "제거" 상태로 변환
            deletedNumber.deleted = true;
            if (count == 0) {
                return count;
            }
        }
        stack.push(number);
    }

    return count;
}

 

이 코드의 경우 스택에서 "꺼내짐"은 "죽음"을 의미한다

 

 

 

2.2 예외 상황 처리

2.2.1 개념

스택을 활용해서 숫자를 완전히 내림차순으로 만들었는데 지워야 하는 숫자의 개수가 남아있는 경우가 있다.

 

예를 들어 다음과 같은 예시가 주어졌다고 하자

 

5자리,

지울 수의 개수  = 3,

숫자 = 54312

 

이 경우 스택을 사용해서 숫자를 지우면 다음과 같아진다.

 

[예외 상황 처리 예_그 1]

 

위에 나온 것 같이 해당 예시는 자릿수 한 개를 제거해서 숫자가 내림차수가 되었다.

이처럼 숫자가 내림차순이 되었는데 지워야 하는 숫자의 개수가 남았을 경우는 뒤에서부터 숫자를 제거해 주면 된다.

이는 내림차순이기에 가장 뒤의 숫자가 작기 때문이다

 

 

[예외 상황 처리 예_그 2]

 

제거해야 할 수의 개수는 2개이기 때문에 뒤에서부터 숫자를 제거하면 54를 얻을 수 있다.

 

 

2.2.2 코드

[deleteRightSideNumber]

public static void deleteRightSideNumber(Number[] numberArr, int count) {

    int index = numberArr.length - 1;
    while (count > 0) {
        Number deletedNumber = numberArr[index];
        //이미 삭제된 숫자면 넘어간다.
        if (deletedNumber.deleted) {
            index--;
            continue;
        }
      	//배열에서 꺼내진 숫자를 제거
        deletedNumber.deleted = true;
        count--;
        index--;
    }
}

 

자릿수가 담긴 numberArr을 받아서 제거해야 하는 숫자의 개수(count)만큼 뒤에서 값을 제거해 준다.

 

 

 

3. 전체 코드

[크게_만들기]

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

public class 크게_만들기 {
    public static class Number {
        int number;
        boolean deleted = false;

        public Number(int number) {
            this.number = number;
        }
    }

    public static int deleteLeftSideNumber(Number[] numberArr, int count) {

        Stack<Number> stack = new Stack<>();

        for (Number number : numberArr) {
            while (!stack.isEmpty() && stack.peek().number < number.number) {
                count--;
                Number deletedNumber = stack.pop();
                deletedNumber.deleted = true;
                if (count == 0) {
                    return count;
                }
            }
            stack.push(number);
        }

        return count;
    }

    public static void deleteRightSideNumber(Number[] numberArr, int count) {

        int index = numberArr.length - 1;
        while (count > 0) {
            Number deletedNumber = numberArr[index];
            if (deletedNumber.deleted) {
                index--;
                continue;
            }
            deletedNumber.deleted = true;
            count--;
            index--;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int size = Integer.parseInt(st.nextToken());
        int count = Integer.parseInt(st.nextToken());

        Number[] numberArr = new Number[size];

        st = new StringTokenizer(br.readLine());
        String totalNumber = st.nextToken();
        for (int i = 0; i < totalNumber.length(); i++) {
            numberArr[i] = new Number(Integer.parseInt(String.valueOf(totalNumber.charAt(i))));
        }

        count = deleteLeftSideNumber(numberArr, count);
        //숫자가 내림차순이 되었는데 제거해야할 숫자의 개수가 남아있을 경우
        if (count > 0) {
            deleteRightSideNumber(numberArr, count);
        }

        StringBuilder sb = new StringBuilder();

        Arrays.stream(numberArr)
                .filter(number -> !number.deleted)
                .forEach(number -> sb.append(number.number));

        System.out.println(sb);
    }
}