-
조건: number는 최대 백만자리 수이므로 굉장히 크다 -> 전체 탐색 불가
-
방법: 가장 큰 수를 만들어야 하므로 앞 자리 수가 큰 것이 무조건 중요하다 -> Greedy 앞에서부터 탐색하면서 현재 숫자보다 더 큰 숫자가 들어오면 현재 숫자를 제거하고 더 큰 숫자로 대체한다. 바로 뒤의 숫자만 이렇게 하는게 아니라
스택으로 그 전의 숫자까지 검사해야 한다(while문 필요). -
종료: k = 0이 되어 종료하거나, 애초에 내림차순 정렬이 되어 있어서 문자열을 다 돌아도 k > 0 인 경우에는 뒤에서부터 k개 만큼 자른다
-
시간효율성: 중첩 루프긴 하지만, 일단 문자열을 한 번 도는 바깥의 for문이
O(n)이고, 그 다음 더 큰 숫자를 만났을 때 pop하는 while문을 생각해도, 이미 append된 숫자가 빠지는 건 최대 한 번이므로2 * O(n)보다 어차피 작게 될 텐데, 상수를 무시하므로O(n)이다.