BOJ - 2812 크게 만들기

Problem

---

Solve

첫번째 풀이

1. 각 숫자 배열로 초기화
2. 크기 기준 내림차순, 위치 기준 오름차순
3. 배열을 순차적으로 돌면서 이전에 선택했던 숫자의 위치보다 크고(자리수가 뒤에) 선택할 수 있는 최소위치 k보다 작은 경우(자리수가 앞에)의 숫자를 선택해서 Queue에 저장한다.
4. 선택할수 있는 최소위치 k가 N인 경우 더 이상 선택할 수 있는 숫자가 없으므로 반복문 종료
5. Queue에 저장된 숫자 String으로 반환.
   시간 복잡도를 고려하지 않고 구현해서 시간초과 발생

두번째 풀이

Dequeue를 사용하여 풀이가 가능하다.

1. 0번째 자리 숫자부터 Dequeue에 저장된 숫자보다 현재 숫자가 더 크고 삭제할수 있는 숫자 개수 k가 남아있다면 현재 숫자보다 작은 숫자를 최대 k개 만큼 삭제하고 현재 숫자를 넣는다.
2. 현재 숫자가 Dequeue에 저장된 숫자보다 작다면 그냥 넣는다.
3. 반복을 끝낸 후 Dequeue에 남아있는 숫자가 N-K보다 많을 수 있기 때문에 Dequeue에 남아있는 숫자를 N-K까지만 꺼내서 반환한다.

설명이 어려워보여서 예시를 보자면
N = 10, K = 4, 4177252841 이 주어졌을때

1. Dequeue = {4}
   • Dequeue가 비어있을 때는 4를 넣어준다.
2. Dequeue = {4,1}
   • 현재 숫자 1은 Dequeue에 들어있는 4보다 작기때문에 Dequeue에 넣어준다.
3. Dequeue = {7}
   • 현재 숫자 7은 Dequeue에 들어있는 4와 1보다 크고 k = 4이기 때문에 2개를 삭제할수 있다.
   • k = 2
4. Dequeue = {7,7}
   • 7은 Dequeue의 7과 같기 때문에 넣어준다.
5. Dequeue = {7,7,2}
   • 2는 7보다 작기 때문에 넣어준다.
6. Dequeue = {7,7,5}
   • 5는 2보다는 크고 7보다는 작기 때문에 2만 삭제해준다.
   • k = 1
7. Dequeue = {7,7,5,2}
   • 2는 5보다 작기때문에 넣어준다.
8. Dequeue = {7,7,5,8}
   • 8은 Dequeue에 있는 모든 숫자보다 크다. 하지만 k가 1이기 때문에 가장 뒤에 있는 2만 삭제할 수 있다.
   • k = 0
9. Dequeue = {7,7,5,8,4}
   • k가 0이기 때문에 더 이상 다른 숫자를 삭제해 줄 수 없다.
10. Dequeue = {7,7,5,8,4,1}

---

Code

public class 크게만들기 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());

		String number = br.readLine();

		Deque<Character> dq = new LinkedList<>();

		int idx = 0;
		int k = K;
		while(idx < N){
        	//현재 숫자
			char num = number.charAt(idx++);

			//삭제할수 있는 개수(k)가 남아있고 Dequeue에 있는 숫자가 현재 숫자보다 작다면 조건을 만족할때까지 삭제
			while(k > 0 && !dq.isEmpty() && dq.getLast() < num){
				dq.pollLast();
                //숫자 삭제시 삭제할수 있는 개수 감소
				k--;
			}
			dq.offerLast(num);
		}

		StringBuilder sb = new StringBuilder();
		for(int i=0;i<N-K;i++){
			sb.append(dq.pollFirst());
		}

		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}
}

시간초과 풀이

public class 크게만들기_첫번째_풀이 {
	static int N;
	static int K;
	static int[] number;
	static List<Number> numbers;
	static Queue<Integer> queue;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());

		String n = br.readLine();
		number = new int[n.length()];
		numbers = new ArrayList<>();
		queue = new LinkedList<>();

		for(int i=0;i<n.length();i++){
			number[i] = Integer.parseInt(String.valueOf(n.charAt(i)));
			numbers.add(new Number(i, number[i]));
		}

		Collections.sort(numbers);

		String answer = start();
		bw.write(answer);
		bw.flush();
		bw.close();
	}

	static void setNumber(){
		int limit = K;
		int prevIdx = 0;

		while(limit < N){
			for(int i=0;i<numbers.size();i++){
				if(numbers.get(i).idx > prevIdx && numbers.get(i).idx <= limit){
					limit++;
					prevIdx = numbers.get(i).idx;
					queue.offer(numbers.get(i).num);
					numbers.remove(numbers.get(i));
					break;
				}else if(numbers.get(i).idx < prevIdx){
					numbers.remove(numbers.get(i));
				}
			}
		}
	}

	static String start(){
		setNumber();

		StringBuilder sb = new StringBuilder();
		while(!queue.isEmpty()){
			sb.append(queue.poll());
		}

		return sb.toString();
	}

	static class Number implements Comparable<Number>{
		int idx;
		int num;
		public Number(int idx, int num){
			this.idx = idx;
			this.num = num;
		}

		@Override
		public int compareTo(Number o1){
			int result = o1.num - this.num;
			if(result == 0){
				result = this.idx - o1.idx;
			}
			return result;
		}
	}
}

---

Result

---

Reference

https://steady-coding.tistory.com/54