[백준 2812번 -그리디] 크게 만들기(자바)

백준 2821번- 그리디 알고리즘

난이도 : 골드 4

 

크게 만들기 

문제

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

10 4
6325712985

출력1

712985

 

입력2

2 1
34

출력2

4

 

입력3

10 9
3254567891

출력3

9

 

입력4

10 9
9876543219

출력4

9

 

입력5

8 3
77766655

출력5

77766

 

입력6

8 3
88888888

출력6

88888

 

 

입력7

8 3
66667777

출력7

67777

 

오답 풀이 :

'뒷수가 앞수보다 크면 앞수 제거'

'숫자가 같거나 뒷수가 크지 않은 경우 제거 못한 갯수만큼 뒷자리 수 제거'

 

풀이계획 :

1. 이중배열 만들기 => arr[i][0]은 값, arr[i][1]은 삭제할지 말지 여부의 플래그로 사용 

2. 현재 인데스의 값 바로 앞 항의 값보다 크면 나보다 작은 값들 루프 돌며 삭제 대상 1로 변경

   (1로 변경할 때 k--; 시켜 k==0까지만 체크)

3. 만약 k>0보다 크면 마지막 k자리 제거

 

시간복잡도 : O(n^2)

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

public class Main{
    
    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());
        String str = br.readLine();
        int[][] arr = new int[n][2];
        int i=0;
        for(char ch : str.toCharArray()){
            arr[i][0]=Integer.valueOf(String.valueOf(ch));
            i++;
        }
        System.out.println(solution(n, k, arr));
    }
    
    public static String solution(int n, int k, int[][] arr){
    	int prevMaxVal=arr[0][0];
    	int prevMaxValIdx=0;
    	loop:for(int i=1; i<n; i++){
        	//뒷수가 앞수보다 클때
            if(arr[i-1][0]<arr[i][0]) {
                //루프로 prevMaxVal까지 탐색하면서 1로 모두 바꾸기
                for(int j=i-1; j>=0; j--){
                	if(arr[j][1]==0 && arr[j][0]<arr[i][0]){
                        arr[j][1]=1;
                        k--;
                        if(k==0) break loop;
                	}
                	if(prevMaxValIdx==j) break;
                }
            }
            if(prevMaxVal<arr[i][0]) {
            	prevMaxVal=arr[i][0];
            	prevMaxValIdx=i;
            	
            }
        }
    	StringBuilder sb = new StringBuilder();
        for(int i=0; i<n; i++) if(arr[i][1]==0) sb.append(arr[i][0]);
    	//뒷수가 앞수보다 큰 경우 없으면 k남을 수 있음
    	if(k>0) {
    		//마지막 k개 제거
    		String ans = sb.toString();
    		return ans.substring(0, ans.length()-k);
    	}
        
        return sb.toString();
    }
    
}

 

평가 : 시간초과, 몇몇 제약조건을 걸어 최대한 루프 탐색 횟수를 줄여보려 했으나 결국 이중 루프 시간 초과 벗어나지 못함.

 

 

정답 풀이 :

최적해를 구하는 방식은 오답풀이 방식과 다르지 않았다.

다만 시간 복잡도를 해결하기 위해 스택을 사용하여 구현한다.

 

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

public class Main{
    
    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());
        String str = br.readLine();
        Integer[] arr = new Integer[n];
        int i=0;
        for(char ch : str.toCharArray()){
            arr[i]=Integer.valueOf(String.valueOf(ch));
            i++;
        }
        System.out.println(solution(n, k, arr));
    }
    
    public static String solution(int n, int k, Integer[] arr){
        Stack<Integer> stk = new Stack<>();
        stk.push(arr[0]);
    	for(int i=1; i<n; i++){
        	//뒷수가 앞수보다 클때
            while(k!=0 && !stk.isEmpty() && stk.peek()<arr[i]) {
                stk.pop();
                k--;
                if(k==0) break;
            }
            stk.push(arr[i]);
        }
        
    	StringBuilder sb = new StringBuilder();
        for(Integer a : stk) sb.append(a);
        String ans = sb.toString();
    	//뒷수가 앞수보다 큰 경우 없으면 k남을 수 있음
    	if(k>0) {
    		//마지막 k개 제거
    		return ans.substring(0, ans.length()-k);
    	}
        
        return sb.toString();
    }
    
}

 

 

 

전체 평가 : 오답풀이와 정답풀이의 로직은 같으나 구현방식에 차이가 있었다. 오답풀이에서는 배열을 이중루프로 돌며 삭제 대상에만 체크를 하고 삭제 대상이 아닌 것들은 건너뛰면서 구현했고 정답풀이는 루프를 돌며 스택에 저장시킨 다음 삭제대상을 삭제하면서 구현했다.

최적해를 구하는 로직과 예외를 포함한 테스트케이스까지 모두 잘 구했음에도 시간초과가 났다. 배열에서 삭제대상이 아닌것은 바로 건너뛰었기때문에 스택에서 이미 삭제대상을 삭제하고 접근하는 것과 시간차이가 크게 날 것이라고 생각하지 못했다.

스택을 통해 432ms 결과가 나왔으니 상당한 차이다.

다른 많은 코테 문제에서도 건너뛰면서 플래그 체크하면서 사용했던 적이 많은데 앞으로 건너뛰는 방식보다 별도의 자료구조에 저장하고 삭제하는 방식을 하나의 선택지로 열어둬야겠다.