[Leetcode] 2434. Using a Robot to Print the Lexicographically Smallest String

https://leetcode.com/problems/using-a-robot-to-print-the-lexicographically-smallest-string/description/

문자열을 주고 문자열의 앞에서 뽑아서 저장하는 연산과, 뽑은 문자열을 출력하는 연산 두 가지를 통해서 사전적으로 가장 작은 문자열을 만드는 문제이다.

처음에는 문자열 뽑아서 저장하다가 갑자기 큰 문자열 나오면 다 비워내고, 다시 저장하는 방식을 사용하면 되겠다 싶어서 그렇게 했다.

from collections import deque

class Solution:
    def robotWithString(self, s: str) -> str:
        answer = []
        tmp = []

        for c in s:
            print(c, tmp, answer)
            while tmp and c > tmp[-1]:
                answer.append(tmp.pop())
            
            tmp.append(c)

        while tmp:
            answer.append(tmp.pop())

        return ''.join(answer)

그런데 3번째 테스트케이스엔 "bdda"에서 "addb"가 나와야하는데 "badd"가 나왔다. 그래서 다른 방법이 필요했다.

힌트에서는 'a'를 만나면 무조건 출력하고, 'a'전에 있던 문자열들은 역순으로 출력되어야한다. 라고 되어 있고, 'a'를 다 사용하면 'b', 'c', 등등에도 같은 원리를 적용해야한다고 적혀있었다.

Counter라는 것을 활용해서 알파벳 별로 갯수를 세고, 가장 작은 문자를 저장할 변수 l을 만들고 그거를 통해서 확인하면서 다 쓰면 l다음 문자를 확인하는 방식으로 갔다.

class Solution:
    def robotWithString(self, s: str) -> str:
        answer = ''
        alpha = Counter(s)

        t = []
        l = 'a'

        for c in s:
            t.append(c)
            alpha[c] -= 1

            while l < 'z' and alpha[l] == 0:
                l = chr(ord(l) + 1)
            
            while t and t[-1] <= l:
                answer += t.pop()

        return answer