99클럽 코테 스터디 27일차 TIL Leetcode Using a Robot to Print the Lexicographically Smallest String

문제 및 조건

풀이 및 코드

아이디어 : 가장 사전순으로 빠른 것을 작다고 표현할 때(아스키 코드로 생각해도 됨), s를 미리 탐색해서, dictionary 형식에 각 알파벳이 몇 개씩 존재하는지 체크한 후, s를 다시 앞에서 부터 하나씩 스택에 넣어준다. 이때 뒤에 남은 알파벳들 중 가장 작은 값이 스택의 마지막 값보다 크면, 스택의 마지막 값이 가장 작은 값 이므로 스택에서 마지막값을 pop 해서 paper에 적어준다. 이 과정을 반복하고, 남은 t의 값들을 reverse해서 더해준다.

 

class Solution:
    def robotWithString(self, s: str) -> str:
        dic={}
        p=""
        for ss in s:
            if dic.get(ss):
                dic[ss]+=1
            else:
                dic[ss]=1
        stack=[]
        for i in range(len(s)):
            fast_alphabet=min(dic.keys())
            while stack and stack[-1]<=fast_alphabet:
                p+=stack.pop()
            if s[i]==fast_alphabet:
                p+=s[i]
            else:
                stack.append(s[i])
            dic[s[i]]-=1
            if dic[s[i]]==0:
                del dic[s[i]]
        return p+"".join(stack)[::-1]