[백준] 2812. 크게 만들기 (골드3) - Stack

2812. 크게 만들기 (골드3)

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	34297	9818	7111	28.005%

문제

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

풀이

• 순서를 유지, 구성요소를 넣고 빼야한다, 다시 넣을 때 그 자리에 다시 넣어야 한다 => Stack
• 앞의 수가 제일 커야한다.

1. 스택이 비어있으면 숫자를 넣고, 스택이 차있으면 자기보다 크거나 같은 수가 나올 때까지 뺀다.
2. 비교 숫자를 스택에 넣는다.
3. k만큼 숫자를 빼서, 넣지 못한 요소가 있으면 나머지 스택에 넣기
4. k만큼 숫자를 빼지 못했을 때, 뒤에서부터 숫자를 빼기 (앞부터 큰 수이기 때문)
5. 스택을 앞에서부터 출력 => get

package codingTest;
import java.io.*;
import java.util.*;
public class Stack_2812 {
	public static void main(String[] args) throws IOException{
		// 2812. 크게 만들기 (골드3)
		
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int N = Integer.parseInt(st.nextToken());	
		int K = Integer.parseInt(st.nextToken());	
		String numStr = bf.readLine();
		String[] numArr= numStr.split("");
		
		/*
		 * 1. 앞자리에 큰 수가 들어가야 한다.
		 * 2. 숫자의 순서는 지켜야 한다.
		 * =>  Stack 사용
		 */
		Stack<Integer> stk = new Stack<Integer>();
		
		int cnt =0;
        
        // 반복문 외부에서 변수를 선언해서, for문이 중간에 끊겨도 밑에서 숫자가 어디까지 왔나 확인한다.
		int i =0; 
        
		for(i=0; i<N; i++) {
			int num = Integer.parseInt(numArr[i]);
			if(cnt==K) break; // 지정 숫자만큼 빼면 반복문 탈출
            
            // 스택이 비었으면 진행x, 먼저 넣어줌
			if(stk.isEmpty()) stk.push(num); 
			else {
            
				/*
				// 한 단계만 검사하는 것이 아니라 앞에까지 끝까지 검사해야한다.
				// 4177252841 (10,4) -> 4775841 (앞에 4 삭제 안됨)
				int stknum = stk.peek();
				if(stknum < num) {
					stk.pop();
					cnt++;
				}
				*/
                
				while(!stk.isEmpty() && cnt<K && stk.peek()<num) {
					stk.pop();
					cnt++; //숫자 뺐으면 k에 도달하기 위한 숫자 증가
				}
                // 스택의 push는 효율성을 위해 조건문 안에 넣거나, 뒷부분으로 뺀다.
				stk.push(num);
			}
		}
		
		
		// cnt가 K보다 커서 뒤의 숫자들을 stack에 담지 못했기 때문에 나머지 숫자들을 stack에 담아준다.
		for(int s=i; s<N; s++) {
			int num = Integer.parseInt(numArr[s]);
			stk.push(num);
		}
		
		// cnt가 K까지 도달하지 못하고 끝났을 때는 뒤의 수부터 하나씩 삭제해 준다.
		/* 
			10 5
			9993333932

			정답 : 99993
			출력 : 999932
		*/
		while(cnt<K) {
			stk.pop();
			cnt++;
		}
		
		StringBuilder sb = new StringBuilder();
		
		for(int j=0; j<stk.size(); j++) {
			sb.append(stk.get(j));
		}
		
		System.out.println(sb);

		bf.close();
	}
}

* for문 변수를 밖에서도 계속 유지하고 싶다면 외부에 변수 선언하기

* while문으로 끝까지 깊게 검사하기 (앞에 peek만 검사하지 않기)