[99클럽 코테 스터디 28일차 TIL] 스택

📖 오늘의 학습 키워드
스택

오늘의 회고

문제

[Using a Robot to Print the Lexicographically Smallest String]
https://leetcode.com/problems/using-a-robot-to-print-the-lexicographically-smallest-string/

나의 해결

class Solution {
    public String robotWithString(String s) {
        int[] count = new int[26];
        StringBuilder answer = new StringBuilder();
        Deque<Character> stack = new ArrayDeque<>();
        char minChar = 'a';
        for (char c : s.toCharArray()) {
            count[c - 'a']++;
        }
        for (char c : s.toCharArray()) {
            count[c - 'a']--;
            stack.push(c);
            while (minChar < 'z' && count[minChar - 'a'] == 0) {
                minChar++;
            }
            while (!stack.isEmpty() && stack.peek() <= minChar) {
                answer.append(stack.pop());
            }
        }
        return answer.toString();
    }
}

1. 각 위치에 알파벳 26자의 개수를 저장할 수 있는 배열 count를 선언한다.
   count[0] : a의 개수
   count[25] : z의 개수
2. 최종적으로 종이에 적힐 문자열을 생성할 StringBuilder answer를 선언한다.
3. stack은 문제에서 설명한 s의 첫 글자를 하나씩 이어 붙여 만든 문자열 t를 나타낸다.
4. 아직 사용되지 않은 문자 중 사전식 순서가 가장 빠른 것을 저장하는 minChar를 a로 초기화한다.
5. for 문을 돌며 s 안 글자의 개수를 count에 나타낸다.
6. for 문을 돌며 s 안 모든 글자에 대해 다음 과정을 반복한다.
   1. 현재 문자의 개수를 하나 줄인다.
   2. 현재 문자를 stack에 추가한다.
   3. minChar의 개수가 0이면, 개수가 0이 아닌 다음으로 순서가 가장 빠른 문자로 값을 갱신한다.
   4. stack이 비어있지 않고 stack의 상단 값(최근에 추가된 값)이 minChar와 같거나 사전 순으로 더 빠르다면 answer의 끝에 stack의 상단 값을 추가하고 stack에서 제거한다.
7. answer를 문자열로 변환해 반환한다.

새로 학습한 내용

Stack vs Deque

Stack

처음에는 Stack 클래스를 이용해 stack을 선언하였다. 그랬더니 실행 시간이 다음과 같았다.

Deque

하지만 다른 코드의 변경 없이 stack 대신 Deque을 사용했더니 실행 시간을 다음과 같이 단축 시킬 수 있었다.

Stack은 동기화된 Vector를 상속받고 동기화 작업으로 인한 오버헤드로 성능 저하가 발생한다. 반면, Deque는 동기화 메커니즘을 사용하지 않아 동기화에 따른 오버헤드가 발생하지 않는다.

참고

Stack vs Deque