https://leetcode.com/problems/remove-duplicate-letters/
Given a string
s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.
- Lexicographical order(사전식 순서): 빠른 알파벳으로 시작하는 단어가 앞에 오되, 맨 앞부터 n자리까지 같은 알파벳이 온다면, n+1에 오는 알파벳이 빠른 단어가 앞에 온다. 만약 단어의 모든 자리가 같은 알파벳이되, 한 단어에 추가적으로 알파벳이 붙어 길이가 더 길다면 짧은 단어가 앞에 온다.
접근 방법 (중첩 for문)
- 의사코드를 이용하여 대략적인 흐름을 구상하였으나, 문자열을 계속 탐색하는 과정에서
for문이 여러번 중첩되면서 실행시간을 초과할 것 같아 중간에 포기하고 다른 방향을 생각해보았다.
의사코드 (stack)
for 알파벳(C) in 문자열(S):
if 확정된 문자열에 C가 있을 경우:
continue
else 확정된 문자열에 C가 없을 경우:
if 남은 S안에 같은 알파벳이 존재하지 않는다면:
C의 자리를 확정하고 확정된 문자열에 C 추가
else 남은 S안에 같은 알파벳이 존재한다면:
if 남은 S안에 더 앞순위의 알파벳이 존재한다면:
C를 삭제
else 남은 S중 C가 가장 앞순위라면:
C의 자리를 확정하고 확정된 문자열에 C 추가
end for
확정된 문자열 출력접근 방법 (stack)
-
시간 내에 풀지 못하여 리트코드에 유저들이 올려준 솔루션과 책의 내용을 참고하였다.
-
문자열의 모든 알파벳마다 확정된 문자열과 남은 문자열을 순회하지 않고, 함수가 실행될 때 미리 문자열을 순회하여
# 문자열을 순서대로 돌며 {문자: 인덱스} 형태의 딕셔너리를 저장한다.
# 딕셔너리가 완성되면, 모든 문자를 Key로, 마지막으로 등장하는 인덱스를 Value로 가지는 딕셔너리가 완성된다.
last = {c: i for i, c in enumerate(s)}
# 파이썬에서 제공하는 collections 모듈의 Counter()를 이용한다.
# Counter()는 hashable한 데이터에서 등장하는 모든 원소의 갯수를 {원소: 갯수} 의 딕셔너리 형태로 돌려준다.
counter = collections.Counter(s)와 같이 해당 문자가 마지막으로 나오는 곳이 어딘지를 체크할 수 있는 데이터를 만들어둔다.
-
'확정된 문자열'(실제로는 확정된 것이 아님)을 담을 수 있는 스택을 하나 만든다.(파이썬에서는 리스트)
-
전체 문자열을 순회하면서 진행하되, 매 알파벳마다 남은 문자열을 전부 순회하여 확정짓는 것이 아니고, 그 알파벳이 문자열의 마지막이라고 가정하고 임시로 규칙대로 '확정된 문자열'에
push한다. -
다음 루프에서 새로운 알파벳이 추가되면, 남은 문자열과 비교하는 것이 아니고 다시 그 알파벳을 마지막으로 하는 문자열이 존재한다고 가정하고 임시로 추가한 '확정된 문자열' 스택의 top 원소와 비교하여 규칙에 어긋나지 않으면 새로운 알파벳을
push하고, 규칙에 어긋난다면 만족될 때 까지 스택을pop하는 방식으로 작동한다. -
이 방식은 매 루프마다 남은 문자열을 확인하지 않으므로, 이번에 들어온 알파벳이 남은 문자열에 존재하는지 아니면 이 번이 마지막인지는 아까 만들어둔
last나counter와 같은 데이터를 사용하여 판별한다. -
이렇게 코딩하면
for문 안에 계속for문을 사용하지 않고,for문 루프 한 번 마다 스택을 조정하는while문 한 번만 쓰면 되므로 런타임이 비약적으로 줄어들게 된다.
의사코드 (recursion)
func(String):
문자열에 포함된 알파벳 오름차순으로 담은 리스트(List(String)) 생성
for 알파벳(C) in List(String):
전체 문자열을 C의 앞부분과 'C를 포함한 뒷부분(Suffix)'으로 나눔
if List(String)과 List(Suffix)가 같다면:
Suffix에서 맨 앞의 C를 제외한 나머지 C를 모두 삭제한 문자열(Mod-Suffix)
return func(Mod-Suffix)
end for
return
end func접근 방법 (recursion)
-
책에서 제시하는 또 다른 접근법으로는 재귀함수가 있었다.
-
이 방식이 위의 스택을 이용한 방식보다 코드를 봤을 때 이해하기가 쉬웠지만, 런타임이 스택을 사용한 것보다 느리게 나왔다.
class Solution:
def removeDuplicateLetters(self, s: str) -> str:
for c in sorted(set(s)):
suffix = s[s.index(c):]
if set(s) == set(suffix):
return c + self.removeDuplicateLetters(suffix.replace(c, ''))
return ''- 리스트의 일부를 순회하는 이중
for문에서for문의 갯수를 줄이기 위해stack을 사용하면 효율적이라는 것을 배웠다. 앞으로 나올 다른 문제들에도 적용시킬 수 있도록 노력해야겠다.
