문제

https://school.programmers.co.kr/learn/courses/30/lessons/42883

요약

문제 내용은 문자열로 숫자가 제공되는데 이숫자중 k 개를 지워서 가장 큰수를 만들어야한다. 단, 숫자의 순서는 바뀌면 않된다.

제약조건
number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
k는 1 이상 number의 자릿수 미만인 자연수입니다.

풀이

완탐을 고려하게되면 10 ^ 6 라는 숫자를 제곱으로돌려야한다.
때문에 한번에 처리할수 있는 방법을 생각해야한다.
최종적으로 가장큰수를 구하기 위해선 앞자리 에 큰수들이 있게 배치해야한다.
입력을 순회하면서 최근 값을 계속 비교하면서 k 개 만큼만 지우면된다.
단순히 비교로 진행될 수 있지만 스텍을 활용하면 최근에 값을 저장하기도 비교하기도 유용하게 할수 있다. 즉 스텍에 최대한의 큰값을 넣는거다.

로직 구현

k 횟수만큼 값이 더 크다면 스텍에 저장된 값을빼고 큰값을 넣는다.
스텍의 값보다 작은 걸 만나면 값을 넣는다.
만약 스텍이 비어 있다면 값을 넣는다.

코드

package programers.makeBigNum.suc;

import java.util.*;

// 큰수만 스텍에 넣는다
public class Solution {
	public String solution(String number, int k) {
		Stack<Integer> stack = new Stack<>();
		int count = k;
		String[] splited = number.split("");
		for (String st : splited) {
			int value = Integer.parseInt(st);
			while (!stack.isEmpty() && stack.peek() < value && count-- > 0) {
				stack.pop();//값이 크다면 최근 값을빼고 값을 넣는다.
			}
			stack.push(value);
		}
		String answer = "";
		System.out.println(k);
		for (int i = 0; i < number.length() - k; i++) {
			answer += stack.get(i);
		}
		return answer;
	}
}

시행착오

처음에 입력들중에 가장 작은 수 k 만큼 정렬해 작은 수를 set 에 넣어 동작 k개 만큼 앞에서 지워나가려 했다.
하지만
반례로 417725, k = 2 가 있다. 이숫자의 가장 작은수 set 은 1,2 인데
그렇게 작은수 잘못된 로직은 4772 를 출력한다 정답(7725).

나중에 든 생각인데 만약 number.length()-k 갯수만큼 set 에 넣게하면
set = {1,2,3,4}, 그리고 k개만 지우개 잘 구현하면 될거 같다는 생각도든다.

import java.util.*;
//정렬하고 len-k 갯수 만큼 추출 돌면서 해당되면 지우기
public class Solution {
	public String solution(String number, int k) {
		// int count = number.length() -k;
		int count = k;
		String [] splited = number.split("");
		PriorityQueue<Integer> q = new PriorityQueue<>();
		for(String s :splited){
			q.offer(Integer.parseInt(s));
		}
		Set<Integer> banSet = new HashSet<>();
		while(count-- > 0){
			banSet.add(q.poll());
		}
		// 제일 작은 len-k 를 구한다 -> 갯수만큼 제외한다...
		// 갯수가 안맞는 경우는? -> 숫자를 뽑아 왔는데 갯수가 부족한경우
		// 많이 있을수 있는데 부족할수 없다 중복된 경우가 많은 경우 작으면 애초에 와일문 에서 성립이 안됨
		int rmCount = k;
		StringBuilder sb = new StringBuilder();
		int idx = 0;
		while(rmCount > 0 && idx < number.length()){
			int value = Integer.parseInt(splited[idx]);
			if(banSet.contains(value)){
				rmCount--;
			}else{
				sb.append(value);// 포함이 안되면 넣어라
			}
			idx++;
		}
		for(;idx < number.length(); idx++){
			sb.append(splited[idx]);
		}
		int totalCount = number.length() - k;
		StringBuilder res = new StringBuilder();
		int resIdx = 0;
		while(totalCount-- >0){
			res.append(sb.toString().charAt(resIdx++));

		}
		System.out.println(banSet);
		return res.toString();
	}
}