[코딩테스트][백준] 🔥 백준 2812번 "크게 만들기" 문제: Python과 Java로 완벽 해결하기! 🔥

🔗 문제 링크

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

🕒 Python 풀이시간: 50분

from collections import deque

n,k=map(int,input().split())
num=list(input())
lastL=len(num)
curL=0
answer=deque([])
for i in range(len(num)):
    if len(answer)==0:
        answer.append(num[i])
        lastL-=1
        curL+=1
        continue
    if lastL+curL<=n-k or int(answer[-1])>=int(num[i]):
        if curL<n-k:
            answer.append(num[i])
            curL+=1
            lastL-=1
    else:
        deleteCnt=0
        while len(answer)!=0 and lastL+curL>n-k and int(answer[-1])<int(num[i]):
            answer.pop()
            curL-=1
        answer.append(num[i])
        curL+=1
        lastL-=1

print("".join(answer))

🕒 Java 풀이시간: 50분

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

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int k=sc.nextInt();
        String[] num=sc.next().split("");
        Stack<String> stack=new Stack<>();
        int lastL=num.length;
        int curL=0;
        for(int i=0;i<num.length;i++){
            if(stack.isEmpty()){
                stack.push(num[i]);
                lastL--;
                curL++;
                continue;
            }
            if(lastL+curL<=n-k||Integer.parseInt(stack.peek())>=Integer.parseInt(num[i])){
                if(curL<n-k){
                    stack.push(num[i]);
                    curL++;
                    lastL--;
                }
            }else{
                while(!stack.isEmpty()&&lastL+curL>n-k&&Integer.parseInt(stack.peek())<Integer.parseInt(num[i])){
                    stack.pop();
                    curL--;
                }
                stack.push(num[i]);
                curL++;
                lastL--;
            }
        }
        StringBuilder sb=new StringBuilder();
        for(int i=0;i<stack.size();i++){
            sb.append(stack.get(i));
        }
        System.out.println(sb.toString());
    }
}

💡 그리디 알고리즘으로 최대 숫자 찾기: 스택을 이용한 O(N) 접근법

해당 N개의 길이로 이루어진 수에서 k개를 제거하여 구할 수 있는 최대 숫자를 구하는 문제이다. 이 때, 자릿수는 k개가 지워지면 동일하기 때문에 앞에서부터 큰숫자를 남기는것이 중요하다고 생각할 수 있다. 그렇기에 우리는 앞자리에 큰 숫자를 가져오기 위해 그리디한 사고라고 생각할 수 있다. 현재 상황에서 최적의 선택을 하는 것이다. 시간복잡도를 따져보면 데이터의 수가 500,000이 최대이기 때문에 최소 O(nlogn)의 연산이나 순환을 한번만 하는 연산을 하는 O(n)이라고 생각할 수 있다. 그렇기에 앞자리에서부터 반복문을 통해 따져가보면서(한번만 순회) 큰수만을 정답을 담는 곳에 남기는 것이다. 이 때, 추가와 해당 담는 곳에 뒤에서만 추가,삭제가 이루어지기 때문에 스택구조를 사용할 수 있다. 만약 정답을 담는 스택에 아무것도 없다면 현재의 수를 일단 담는다. 그리고 스택의 길이(정답의 길이)와 아직 탐색하지 않은 수의 갯수를 통해 전체 길이가 N-K가 되도록 조젏한다. 현재 탐색하는 수가 스택에 있는 peek의 수, 즉 담았을 때 바로 앞에 오는 수보다 크거나 같으면 담고 남은 수가 우리가 구해야하는 수의 길이(N-K)보다 짧으면 수의 길이를 완성시켜야하므로 담는다. 그 외의 상황에서 바로 앞의 숫자보다 큰 숫자가 현재의 수로 오면 스택에서 현재의 수보다 큰수가 나오거나 N-K의 길이보다 짧아지지 않을 때까지 스택에서 지운다. 그런 다음 현재의 수를 넣으면된다. 이렇게 구한 스택이 정답을 담고 있는 숫자열이된다.

이렇게 Python과 Java로 백준의 "크게 만들기" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊