“파이썬 알고리즘 인터뷰” + https://leetcode.com/problems/remove-duplicate-letters/
주어진 문자열에서 중복된 문자를 제거해서 각 문자가 하나만 있도록 해야한다. 결과는 “lexicographical order”가 되어야 하는데 이 부분이 좀 어렵다. 중복된 문자를 없애는 건 알겠는데 “사전정의의 순으로”라는 게 도통 이해가 가지 않았다. “cbacdcbc”가 입력일 때 정답은 “acdb”라는데 어떻게 그렇게 되는 건지 와닿지가 않아서 책의 풀이를 보고서야 약간은 알 것 같은 느낌? 중복된 문자를 제거하되 알파벳 순서에 맞게 제거할 문자를 선택을 해야하는데 이걸 글로 잘 설명할 수가 없네??? 아직도 내 것이 되지 않았기 때문일 것이다.
매번 생각하는 거지만 책 내용이 꽤 불친절하다. 마치 그냥 이렇게 하면 된다. 쉽지? 라는 것 같달까. 어떻게 그런 알고리즘이 도출되는지 설명하지 않고 냅다 풀이 방법을 던지는데다 리트코드에 나와 있는 문제와 다르게 책에 옮겨진 문제는 그냥 간략하게 요약돼 있을 뿐이라 바로 이해가 되지 않는 경우가 많다. 굉장히 오만한 책이라고 생각한다. 그래서 기분 나쁠 때가 있다.
- “cbacdcbc”에서 처음의 c는 뒤에서도 등장하므로 제거 가능, b도 뒤에 중복이 있으므로 지워도 됨. (중간의 a가 하나만 있는데다 사전정의로 a 앞에 c와 b가 있을 수 없으니까 앞의 cb를 지운 듯)
- 앞의 cb를 지운 “acdcbc”에서 a는 하나만 있으므로 그대로 유지 -> “a”
- “acdcbc”에서 두 번째의 c는 뒤에 중복된 c가 두 개나 더 있지만, 사전정의 순으로서 하나만 있는 d의 뒤에 올 수 없으므로 첫 번째 c만 남긴다. -> “ac”
- “acdb”에서 d도 하나만 있으므로 그대로 유지. -> “acd”
- “acdb”에서 b가 d 뒤에 있지만 하나만 남았으므로 그대로 유지. -> “acdb”
…솔직히 이걸 코드로 작성하려니 아직도 잘 모르겠다. 아무튼 재귀로 푼 것이 removeDuplicateLetters1()이고 스택을 이용한 풀이가 removeDuplicateLetters2()이다. 방금 적은 풀이대로라면 재귀 방식이 훨씬 나아 보인다. 책에서도 말하지만 스택 방식은 스택을 써서 풀 수 있어서 활용했다 뿐이지 카운터를 쓴다거나 stack[-1] 검색을 하므로 파이썬스러운 방법이다.
def removeDuplicateLetters1(self, s: str) -> str:
for char in sorted(set(s)):
suffix = s[s.index(char):]
if set(s) == set(suffix):
return char + self.removeDuplicateLetters1(suffix.replace(char,''))
return ''
def removeDuplicateLetters2(self, s: str) -> str:
counter, seen, stack = collections.Counter(s), set(), []
for char in s:
counter[char] -= 1
if char in seen:
continue
while stack and char < stack[-1] and counter[stack[-1]] > 0:
seen.remove(stack.pop())
stack.append(char)
seen.add(char)
return ''.join(stack)재귀에서 보면 결국 알파벳 순서로서 가장 작은 문자(여기서는 a) 앞에 온 중복된 문자들(여기서는 cb)는 필요가 없으므로 시작부터 고려하지 않아도 된다. 그리고 그 가장 작은 문자를 기준으로 뒷부분 문자열(suffix)을 대상으로 중복 제거를 해나간다.
for char in sorted(set(s)):
전체 문자열을 정렬해 하나씩 기준점으로 삼는다. (여기서는 a -> b -> c -> d)suffix = s[s.index(char):]
기준점부터 끝까지의 문자열(acdcbc)을 대상으로if set(s) == set(suffix):
중복이 없다면return char + self.removeDuplicateLetters1(suffix.replace(char,''))
기준점 문자를 남기고 나머지 문자열에서 같은 처리를 실행한다.
다시 풀어보라고 하면 자신은 없지만 어느정도 이해는 간다. 반면 스택을 이용한 풀이는 재귀에 비하면 억지스러운 느낌도 없지 않다.
counter, seen, stack = collections.Counter(s), set(), []
문자열의 각 문자 갯수를 저장하는 Counter, 등장한 적 있는 문자를 저장하는 세트 seen, 스택 stackfor char in s:
문자 하나 씩 반복하며counter[char] -= 1
해당 문자의 카운터를 -1 한다.if char in seen: continue
지금까지 등장한 적이 있는 문자라면 다음 문자로 이동while stack and char < stack[-1] and counter[stack[-1]] > 0:
아니라면, “스택이 비어 있지 않고” 해당 문자가 “스택에 최근 저장된 문자보다 사전적으로 우선이고” “스택의 최근 문자가 앞으로 하나 이상 존재한다면” 중복이므로 그런 문자가 스택에 없을 때까지 지운다. seen.remove(stack.pop())stack.append(char)
seen.add(char)
해당 문자를 스택에 쌓고 본 적 있는 문자로 등록한다.return ''.join(stack)
마지막에 남은 스택의 문자들을 join해서 반환한다.
문제를 제대로 이해하지 않으면 풀이조차 이해가 안 가는 어려운 편이었다. 외국에선 이런 게 익숙한가?