중복 문자 제거
문제
중복된 문자를 제외하고 사전식 순서로 나열하라.
예제1
- 입력 "bcabc", 출력 "abc"
예제2
- 입력 "cbacdcbc", 출력 "acdb"
코드
정답
# 재귀
class Solution:
def removeDuplicateLetters(self, s: str) -> str:
# 집합으로 정렬
for char in sorted(set(s)):
suffix = s[s.index(char):]
# 전체 집합과 접미사 집합이 일치할때 분리 진행
if set(s) == set(suffix):
return char + self.removeDuplicateLetters(suffix.replace(char, ''))
return ''
# 스택
import collections
class Solution:
def removeDuplicateLetters(self, s: str) -> str:
counter, stack = collections.Counter(s), []
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)
see.add(char)
return ''.join(stack)풀이코드
# import pprint
class Solution:
def __init__(self):
self.count = 0
def removeDuplicateLetters(self, s: str) -> str:
print()
print(f'{self.count}번째 재귀함수')
print(f's = {s}')
self.count += 1
tmp = 1
for char in sorted(set(s)):
print(f'{tmp}번째 for문 sorted(set(s)) : {sorted(set(s))}')
tmp += 1
suffix = s[s.index(char):]
print(f'char = {char}')
print(f'suffix = {suffix}')
print(f'set(s) = {set(s)}')
print(f'set(suffix) = {set(suffix)}')
if set(s) == set(suffix):
return char + self.removeDuplicateLetters(suffix.replace(char, ''))
return ''
answer1 = Solution().removeDuplicateLetters("bcabc")
print(f'answer : {answer1}')
answer2 = Solution().removeDuplicateLetters("cbacdcbc")
print(f'answer : {answer2}')
answer3 = Solution().removeDuplicateLetters("ebcabc")
print(f'answer : {answer3}')
answer4 = Solution().removeDuplicateLetters("ebcabce")
print(f'answer : {answer4}')풀이
문제를 이해하기 조금 어려웠다. 중복 문자를 없애고 사전식 순서로 나열해야한다. 문자열의 위치를 이동시키면 안된다. 두 번째 예제에서 cbacdcbc에서 abcd가 아닌 acdb가 와야한다. 첫 번째 예제에서 만약 앞에 e 문자가 하나 더 붙은 ebcabc가 입력값이라면 결과는 eabc가 될 것이다. e 문자 자체는 해당 문자열 내에서 사전 순으로는 가장 뒤에 있지만, e는 입력 값에서 딱 한 번만 등장하고 a, b, c는 뒤이어 등장하기 때문에 e의 위치를 변경할 수 없기 때문이다. 반면 입력 값이 ebcabce라면 첫 번째 e는 중복으로 제거할 수 있고 마지막 e를 남겨서, 결과는 abce가 될 수 있을것이다.
재귀함수 풀이
문자열이 들어오면 먼저 중복을 제거하고 알파벳 순으로 정렬시킨다.
sorted(set(s))이렇게 정렬된 문자열을 한 문자씩 차례로 for문을 돌면서 중복이 제거하지 않은 기존의 문자열에서 찾아 해당 문자부터 끝까지 접미사(suffix)로 빼낸다.
suffix = s[s.index(char):]분리 가능 여부는 전체 집합과 접미사 집합이 일치하는지 여부로 판별한다. 왜냐하면 집합은 중복된 문자가 제거된 자료형이므로, 전체 집합이 접미사 집합과 같게 된다면 접미사 집합에도 중복을 제거한 유일한 문자열들이 다 포함이 되어 있다는 말이므로 suffix를 떼어올 수 있다. 그리고 현재 위에서 정렬된 문자열로 for문을 돌고 있으므로 suffix의 맨 첫번째 문자를 반환시키고 그 문자를 모두 없애버린 suffix를 인자로 재귀호출을 해서 정답을 얻을 수 있다.
if set(s) == set(suffix):
return char + self.removeDuplicateLetters(suffix.replace(char, ''))재귀 함수 호출과 for문 안에서의 변수 값이 변화하는 과정은 이러하다.
"""
input : bcabc
0번째 재귀함수
s = bcabc
1번째 for문 sorted(set(s)) : ['a', 'b', 'c']
char = a
suffix = abc
set(s) = {'b', 'c', 'a'}
set(suffix) = {'b', 'c', 'a'}
1번째 재귀함수
s = bc
1번째 for문 sorted(set(s)) : ['b', 'c']
char = b
suffix = bc
set(s) = {'b', 'c'}
set(suffix) = {'b', 'c'}
2번째 재귀함수
s = c
1번째 for문 sorted(set(s)) : ['c']
char = c
suffix = c
set(s) = {'c'}
set(suffix) = {'c'}
3번째 재귀함수
s =
answer : abc"""
input : cbacdcbc
0번째 재귀함수
s = cbacdcbc
1번째 for문 sorted(set(s)) : ['a', 'b', 'c', 'd']
char = a
suffix = acdcbc
set(s) = {'b', 'c', 'd', 'a'}
set(suffix) = {'b', 'c', 'd', 'a'}
1번째 재귀함수
s = cdcbc
1번째 for문 sorted(set(s)) : ['b', 'c', 'd']
char = b
suffix = bc
set(s) = {'b', 'c', 'd'}
set(suffix) = {'b', 'c'}
2번째 for문 sorted(set(s)) : ['b', 'c', 'd']
char = c
suffix = cdcbc
set(s) = {'b', 'c', 'd'}
set(suffix) = {'b', 'c', 'd'}
2번째 재귀함수
s = db
1번째 for문 sorted(set(s)) : ['b', 'd']
char = b
suffix = b
set(s) = {'b', 'd'}
set(suffix) = {'b'}
2번째 for문 sorted(set(s)) : ['b', 'd']
char = d
suffix = db
set(s) = {'b', 'd'}
set(suffix) = {'b', 'd'}
3번째 재귀함수
s = b
1번째 for문 sorted(set(s)) : ['b']
char = b
suffix = b
set(s) = {'b'}
set(suffix) = {'b'}
4번째 재귀함수
s =
answer : acdb
""""""
input : ebcabc
0번째 재귀함수
s = ebcabc
1번째 for문 sorted(set(s)) : ['a', 'b', 'c', 'e']
char = a
suffix = abc
set(s) = {'b', 'c', 'a', 'e'}
set(suffix) = {'b', 'c', 'a'}
2번째 for문 sorted(set(s)) : ['a', 'b', 'c', 'e']
char = b
suffix = bcabc
set(s) = {'b', 'c', 'a', 'e'}
set(suffix) = {'b', 'c', 'a'}
3번째 for문 sorted(set(s)) : ['a', 'b', 'c', 'e']
char = c
suffix = cabc
set(s) = {'b', 'c', 'a', 'e'}
set(suffix) = {'b', 'c', 'a'}
4번째 for문 sorted(set(s)) : ['a', 'b', 'c', 'e']
char = e
suffix = ebcabc
set(s) = {'b', 'c', 'a', 'e'}
set(suffix) = {'b', 'c', 'a', 'e'}
1번째 재귀함수
s = bcabc
1번째 for문 sorted(set(s)) : ['a', 'b', 'c']
char = a
suffix = abc
set(s) = {'b', 'c', 'a'}
set(suffix) = {'b', 'c', 'a'}
2번째 재귀함수
s = bc
1번째 for문 sorted(set(s)) : ['b', 'c']
char = b
suffix = bc
set(s) = {'b', 'c'}
set(suffix) = {'b', 'c'}
3번째 재귀함수
s = c
1번째 for문 sorted(set(s)) : ['c']
char = c
suffix = c
set(s) = {'c'}
set(suffix) = {'c'}
4번째 재귀함수
s =
answer : eabc
""""""
input : ebcabce
0번째 재귀함수
s = ebcabce
1번째 for문 sorted(set(s)) : ['a', 'b', 'c', 'e']
char = a
suffix = abce
set(s) = {'b', 'c', 'a', 'e'}
set(suffix) = {'b', 'c', 'a', 'e'}
1번째 재귀함수
s = bce
1번째 for문 sorted(set(s)) : ['b', 'c', 'e']
char = b
suffix = bce
set(s) = {'b', 'c', 'e'}
set(suffix) = {'b', 'c', 'e'}
2번째 재귀함수
s = ce
1번째 for문 sorted(set(s)) : ['c', 'e']
char = c
suffix = ce
set(s) = {'c', 'e'}
set(suffix) = {'c', 'e'}
3번째 재귀함수
s = e
1번째 for문 sorted(set(s)) : ['e']
char = e
suffix = e
set(s) = {'e'}
set(suffix) = {'e'}
4번째 재귀함수
s =
answer : abce
"""스택 풀이
들어온 문자열을 순서대로 카운트된 객체에서 하나씩 줄여나가면서 for문을 돌게된다.
for char in s:
counter[char] -= 1여기서 seen은 집합 자료형으로 이미 처리된 문자 여부를 확인하기 위해 사용했으며, 이처럼 이미 처리된 문자는 스킵한다. 스택이라면 in이라는 연산을 사용할 수 없기 때문에 별도의 집합 자료형을 사용했다. 사실은 여기서 스택으로 가정하고 사용한 파이썬의 자료형은 리스트이고, 리스트는 검색도 잘 지원하기 때문에 굳이 스택이라는 자료 구조로 한정 짓지 않고 풀이한다면 seen 변수 없이도 풀이가 가능하다.
if char in seen:
continue현재 for문의 char의 문자와 stack에 있는 가장 최근 문자 stack[-1]를 비교하여 stack[-1]이 더 사전순에서 뒤쪽 문자열이라면 잘못되었기 때문에 stack[-1]을 제거한다.(ex : char이 b인데 stack[-1]이 c일 때)
while stack and char < stack[-1] and counter[stack[-1]> 0:
seen.remove(stack.pop())아닐경우 계속 스택에 쌓아 출력한다.
stack.append(char)
seen.add(char)
return ''.join(stack)
출처
파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]