leetcode medium : Using a Robot to Print the Lexicographically Smallest String

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

 

class Solution:
    def robotWithString(self, s: str) -> str:
        counter = Counter(s)
        t = [] # stack
        answer = ''
        for ch in s:
            #first operation
            t.append(ch)
            if counter[ch] == 1:
                del counter[ch]
            else:
                counter[ch] -= 1
                
            # second operation
            while counter and t and min(counter.keys()) >= t[-1]:
                answer += t.pop()
        
        # add remaining
        while t:
            answer += t.pop()
                
        return answer

일단 문자열을 쭉 스캔해서 알파벳 개수를 센다.

무조건 s의 문자를 t에 넣어야 뭐가 진행이된다. 안넣으면 안됨. 그래서 순서대로 스캔하면서 일단 한글자를 넣는다 (first operation)

그리고 매 순간 t에서 문자를 얼마나 빼서 answer에 추가할지 결정해서 넣는다.

while counter : s에 아직 스캔하지 않은 글자가 남아있고

while t : 스택이 비어있지 않으며

min(counter.keys()) >= t[-1] : 스캔하지 않은 글자중에 젤 작은게 현재 스택 top보다 작거나 같으면

answer += t.pop() : 스택 top이 남은 글자들보다 클때까지 계속 빼서 answer에 넣는다.

즉 남은 글자들보다 무조건 작은 글자는 바로 정답에 넣고

스택에는 남은 글자들보다 큰 글자들만 유지하는 것이다.

 

다시 말하자면, 큰 글자는 보관하고 작은 글자는 정답에 추가해서 smallest한 문자열을 만드는 것이다.