Algorithm, boj, 크게만들기(2812)
문제유형
- greedy
해결
- 처음도전 실패
- 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();
}
}