참고
문제해설
문제 로직고민
NOTE
•
문자열을 모두 순회하면서 다음 숫자가 지금보다 크다면, 현재 문자열을 제거한다.
◦
모든 문자열을 순회하면서 제거해야하는 경우를 판단한다.
◦
만약 현재보다 다음숫자가 크다면, 현재문자부터 시작문자까지의 범위를 다음 숫자와 비교해 작으면 제거한다.
◦
만약 제거횟수를 모두 사용하면 순횐을 멈추고, 문자열을 생성한다.
◦
만약 제거횟수를 모두 사용하지 못했으면, 문자열 생성시 사용하지 못한만큼 순회를 줄인다.
작성코드
NOTE
class Solution {
public String solution(String number, int k) {
StringBuilder sb = new StringBuilder();
int cnt = 0;
boolean[] visited = new boolean[number.length()];
for(int idx=0; idx<number.length()-1; idx++){
if(cnt == k) break;
char numCur = number.charAt(idx);
char numNext = number.charAt(idx+1);
if(numCur < numNext){
for(int j=idx; j>=0; j--){
numCur = number.charAt(j);
if(numCur >= numNext || cnt == k) break;
if(visited[j]) continue;
cnt++;
visited[j] = true;
}
}
}
for(int i =0; i<number.length() - Math.abs(k-cnt); i++){
if(!visited[i]) sb.append(number.charAt(i));
}
return sb.toString();
}
}
Java
복사
생각보다 까다로웠던 문제
다른사람 풀이
NOTE
import java.util.Stack;
class Solution {
public String solution(String number, int k) {
char[] result = new char[number.length() - k];
Stack<Character> stack = new Stack<>();
// stack에 넣으면서 진행
for (int i=0; i<number.length(); i++) {
char c = number.charAt(i);
while (!stack.isEmpty() && stack.peek() < c && k-- > 0) {
stack.pop();
}
stack.push(c);
}
// 제거길이 만큼만 출력
for (int i=0; i<result.length; i++) {
result[i] = stack.get(i);
}
return new String(result);
}
}
Java
복사
Stack 자료구조 할용 (visited를 안써서 더 효율적)