[99클럽 코테 스터디 23일차 TIL] 문자열

qk·2024년 6월 19일
0

회고

목록 보기
23/33
post-thumbnail
post-custom-banner

📖 오늘의 학습 키워드
문자열

오늘의 회고

문제

[Remove K Digits]
https://leetcode.com/problems/remove-k-digits/description/

나의 해결

class Solution {
    public String removeKdigits(String num, int k) {
        if (num.length() <= k)  {
            return "0";
        }
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < num.length(); i++) {
            while(!stack.isEmpty() && stack.peek() > num.charAt(i) && k > 0) {
                stack.pop();
                k--;
            }
            stack.push(num.charAt(i));
        }
        while (k > 0){ 
            stack.pop();
            k--;
        }
        StringBuilder answer = new StringBuilder();
        for (Character c : stack) {
            answer.append(c);    
        }
        while(answer.length() > 1 && answer.charAt(0) == '0'){ 
            answer.deleteCharAt(0);
        }
        return answer.toString();
    }
}
  1. 제거해야 하는 숫자의 개수가 num의 길이보다 크거나 같으면 "0"을 반환한다.
  2. for문을 돌며 각 자릿수를 스택에 넣는다. 만약 해당 순서에 넣어야 할 숫자보다 스택의 최상단 값이 더 크다면 그 값을 제거하고 k의 값을 하나 줄인다. 이를 스택에 값이 존재하고 최상단 값이 더 크며 k 값이 0보다 클 때까지 반복한다.
  3. 2번 과정 이후에도 k 값이 0이 되지 않았다면 남은 k 번만큼 stack의 최상단 숫자들을 제거한다.
    • 앞자리 숫자보다 뒷자리 숫자(stack의 상단)의 크기가 더 크다는 것이 보장되어 있다.
  4. stack 안 남은 숫자를 answer에 추가한다.
  5. 숫자 맨 앞에 0이 오면 안 되므로 answer 맨 앞쪽에 위치한 0의 범위를 구하고 이를 포함하지 않은 문자열을 반환한다.

새로 학습한 내용

실행 시간 단축하기

while(!stack.isEmpty()) {
	answer.insert(0, stack.pop());
}
stack 안에 남은 숫자를 answer에 추가할 때, 처음에는 stack에서 pop해서 answer 맨 앞에 추가하는 방식으로 진행했다.
for (Character c : stack) {
	answer.append(c);    
}
위 코드에서 for문을 이용해 stack 안 숫자를 들어간 순서대로 그대로 꺼내는 방식으로 수정하니 다음과 같이 실행 시간을 단축할 수 있었다.
post-custom-banner

0개의 댓글