Algorithm, boj, 크게만들기(2812)

문제유형

• greedy

  해결

  1. 처음도전 실패
  • 3자리를 뽑는 거라면 0부터 전체길이-3까지 중 가장큰수를 찾고, 그 가장 큰 수 다음부터 전체길이-2까지 중 가장큰수찾고…이런식으로 구했는데 (1 ≤ K < N ≤ 500,000) 이 조건 때문에 당연히 실패할것같았다 2. 스택을 이용해서 구현하려고 했으나 마지막에 결과값을 반대로 출력해야 하는것이 막혀서 deque로 뽑기로했다

3.

• 큐가 비어있으면 큐에 숫자를 추가하고,
• 큐가 비어있지않으면 큐의 마지막 숫자와 들어갈 숫자를 비교한다
• 들어갈 숫자가 더 크다면 마지막 숫자를 제거하고, 삭제할 숫자k–를 해준다
  • 삭제할 숫자가 남아있고 큐가 비어있지 않을때가지 해당 비교문을 수행한다

한줄평

• deque를 처음 공부하게되었다
• 첫째. 스택,큐를 이용해서 풀려는 시도를 못했다
• 둘째. 문제 풀이 방식을 코드화 해내지 못했다

package org.baekjoon;

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

public class test2812_greedy_makeBig {

	public static void main(String[] args) throws IOException {

		int n,k;
		String s;
		char[] temp;
		Deque<Integer> dq = new LinkedList<Integer>();

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		s = br.readLine();

		for (int i=0; i<n; i++) {

			// k : 제거할 수 , 큐가 비어있지않을때  / 새로들어올 수가 마지막 숫자보다 작거나 같을때까지 마지막 숫자 삭제
			while (k>0 && !dq.isEmpty() && dq.peekLast() < s.charAt(i) - '0') {
				dq.removeLast();
				--k;	// 숫자를 제거 했으므로 k--해준다
			}

			dq.addLast(s.charAt(i) - '0');
		}

		while(!dq.isEmpty() && n-k > 0) {
			bw.write(String.valueOf(dq.pollFirst()));
			++k;
		}
		bw.flush();
		bw.close();
	}

}

---

Reference

• 문제보러가기
• https://hsdevelopment.tistory.com/494

---