[백준] 크게 만들기

문제 주소

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

 

 

문제 설명

N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000)

둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다.

출력

입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다.

예제 입력 1

4 2
1924

예제 출력 1

94

예제 입력 2

7 3
1231234

예제 출력 2

3234

예제 입력 3

10 4
4177252841

예제 출력 3

775841

 

 

제출 코드 1

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

public class Main {

    static char[] number;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        number = br.readLine().toCharArray();

        int[] index = new int[N - K];
        int largestIndex = -1;
        int start = 0;

        for (int i = 0; i < index.length; i++) {
            int end = K + i;
            largestIndex = findLargest(start, end, largestIndex);
            index[i] = largestIndex;
            start = largestIndex + 1;
        }

        StringBuilder sb = new StringBuilder();
        for (int i : index) {
            sb.append(number[i]);
        }
        System.out.println(sb);
    }

    static int findLargest(int start, int end, int prevLargestIndex) {
        if (prevLargestIndex >= start) {
            // 이전 최대인덱스가 탐색 범위 안에 없으면
            for (int i = prevLargestIndex + 1; i <= end; i++) {
                if (number[i] > number[prevLargestIndex]) {
                    prevLargestIndex = i;
                }
            }
            return prevLargestIndex;
        } else {
            //처음부터 최대 인덱스를 찾는다
            int largestIndex = start;
            for (int i = start; i <= end; i++) {
                if (number[i] > number[largestIndex]) {
                    largestIndex = i;
                }
            }
            return largestIndex;
        }
    }
}

 

코드 1 설명

원래 이렇게 짰는데 시간이 초과되어서 시간을 줄일 수 있는 방법을 찾아보다가 저렇게 케이스 분리를 했다

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

public class Main {

    static char[] number;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        number = br.readLine().toCharArray();

        int[] index = new int[N - K];
        int largestIndex = -1;

        for (int i = 0; i < index.length; i++) {
            largestIndex = findLargest(largestIndex + 1, K + i);
            index[i] = largestIndex;
        }

        StringBuilder sb = new StringBuilder();
        for (int i : index) {
            sb.append(number[i]);
        }
        System.out.println(sb);
    }

    static int findLargest(int start, int end) {
        int largestIndex = start;
        for (int i = start; i <= end; i++) {
            if (number[i] > number[largestIndex]) {
                largestIndex = i;
            }
        }
        return largestIndex;
    }
}

 

뒤에서 N-K를 넘어가서 처음 것을 고르게 되면 차례대로 다 골라도 숫자가 모자라게 된다

그래서 앞에서부터 K + i (N-(N-K)+i)인곳까지 안에서만 숫자를 골라야 한다

그 중에서 가장 큰 것을 골라서 넣어주게 코드를 짰는데

자꾸 시간초과가 되어서 케이스 분리를 해서 조금 더 빠르게 해줬더니 통과했다

 

 

다른사람의 풀이

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int K = Integer.parseInt(input[1]);

        String number = br.readLine();

        System.out.println(findLargestNumber(N, K, number));
    }

    public static String findLargestNumber(int N, int K, String number) {
        Stack<Character> stack = new Stack<>();
        int toRemove = K;

        for (int i = 0; i < N; i++) {
            char current = number.charAt(i);
            while (!stack.isEmpty() && toRemove > 0 && stack.peek() < current) {
                stack.pop();
                toRemove--;
            }
            stack.push(current);
        }

        // 만약 아직 지워야 할 숫자가 남아있는 경우 뒤에서부터 지움
        while (toRemove > 0) {
            stack.pop();
            toRemove--;
        }

        // 스택의 내용을 문자열로 변환
        StringBuilder sb = new StringBuilder();
        for (char c : stack) {
            sb.append(c);
        }

        return sb.toString();
    }
}

 

풀이 설명

스택을 활용해서 풀었다 -> 이게 위보다 나은 풀이인것 같다...

숫자를 하나하나 보면서 

 

스택이 비어있지 않고 제거해야할 숫자가 남아있으면 (toRemove>K)

그리고 스택의 맨 위 숫자가 현재 숫자보다 작으면

맨 위의 숫자를 제거해준다

숫자를 하나 줄였으니까 toRemove를 1 감소시킨다

 

현재 숫자를 스택에 추가한다

 

모든 숫자를 처리한 후에도 제거해야 할 숫자가 남아있다면 스택의 뒤쪽에서부터 숫자를 제거한다