316. Remove Duplicate Letters

주어진 문자열에서 중복을 제거하고, 사전순으로 배치하는 문제

 

위 문제 처음 봤을 때는 for문으로 진행하면서 stack에 들어 있는지 파악하고, 없으면 push

중복 문자면 pop을 하면 된다고 생각했다. 그리고 sort해서 출력하면 되겠지 했다. 

 

왜냐하면 예제 1번을 보면 그렇게 해석될 수밖에 없었다. 

Input: s = "bcabc" Output: "abc"

 

하지만 예제 2번에서 내가 생각한 방법대로 하면 절대로 값이 안나오는 것이다. 

Input: s = "cbacdcbc" Output: "acdb"

 

만약 내가 생각한대로 했다면 abcd가 된다. (사전순으로 정렬하므로)

 

2번 예제로 풀어보면, for문으로 s를 돌면서 

 

1) 현재 값이 이미 포함되어 있는지 확인한다 -> 후순위로 밀리면 사전순에서 밀림, 포함되어 있으면 건너뜀

2) 포함되어 있지 않다면 현재 문자가 stack의 top보다 작은지 확인한다. 

3) stack의 top 값이 현재 문자 위치 다음 부터 s의 끝값까지 같은 문자열이 있는지 확인한다.

 

2),3)을 만족하면 stack의 top을 pop시킨다. 

 

    def removeDuplicateLetters(self, s: str) -> str:
        '''
        처음 풀이...중복제거후 사전순 정렬인지 알았다.
        lst = []
        for k, v in collections.Counter(s).items():
            if k not in lst:
                lst.append(k)
        lst.sort()
        return ''.join(lst)
        '''
        ans = []
        for i in range(len(s)):
            if s[i] in ans:
                continue
            while ans  and s[i] < ans[-1] and ans[-1] in s[i+1:]:
                ans.pop()
            ans.append(s[i])
        return "".join(ans)