[자료구조/스택] 중복된 문자를 제외하고 사전식 순서로 나열

참조 url : https://leetcode.com/problems/remove-duplicate-letters/

Example 1:

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

Example 2:

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

 

문제 풀이를 위한 해설 특징

• 사전식 순서의 적용은 중복된 문자에만 적용된다
• 그러다 보니 중복을 제거하고 나머지 문자에 대해 사전식으로 정렬하는 것이 아니라 중복이 아닌 문자의 위치는 그대로 있는 상황 속에서 나머지 중복문자들만 하나만 남기고 사전식으로 정렬해야 한다
• 예를 들어 bcabc 라는 문자의 중복문자를 제외하면 사전에서 제일 먼저 찾을 수 있는 순으로 나열하면 abc 일 것이다.
• 만약 e가 붙은 ebcabc라면 eabc가 남을 것이고 e가 중복으로 붙는다면 ebcabce 에서 e가 중복으로 제거 되어 abce로 남을 것이다

 

재귀 함수를 활용한 풀이 1

• 일반적인 재귀 함수를 활용하여 풀이
• 실행 속도 : 49 ms

스택을 활용한 풀이 2

• 현재 문자(char)가 스택에 쌓여 있는 문자(이전 문자보다 앞선 문자) and 뒤에 붙일 문자가 남아 있다면(즉, counter가 0이라면), 스택에 쌓아 놓은 걸 없앤다
• 문자별 개수를 counting하기 위해 collections.Couter() 라이브러리 사용
• 이미 처리된 문자 여부를 확인할 집합(set) 데이터도 필요하다.
• 스택 연산에서 정의한 기능 외 python 리스트 자료구조의 특성을 이용한 풀이 version
• 실행 속도 : 36 ms

 

스택을 활용한 풀이 3

• 스택에서 가능한 연산만을 활용해서 풀이
• seen 집합에서 검색 기능 수행

 

총평

• 현재 문제를 정확하게 이해하지 못했고, 특별히 코드 중에 while문으로 다음 문자를 확인하는 부분이 있는데 왜 이런 로직이 사용됐는지 정확히 미파악
• python의 리스트로 스택을 구현했으며 pop() 메서드를 통해 스택 자료구조 특징을 사용했다.