반응형
https://leetcode.com/problems/remove-duplicate-letters/
Think
재귀는 많이 연습해야 겠다..
함수 만들어서 재귀로 푸는 거에 쫄지 말기.
스택으로 푸는 법도 다시 풀어보기.
Solution
1. 재귀
class Solution(object):
def removeDuplicateLetters(self, s):
"""
:type s: str
:rtype: str
"""
#현재의 전체 집합에서 정렬된 앞에서부터 한글자씩 체크
for char in sorted(set(s)) :
#체크할 char의 suffix집합 생성(슬라이싱)
suffix = s[s.index(char):]
#전체집합 == suffix집합이면 suffix만 남기고 분리 후 return (suffix에서 현재 char는 삭제)
# != 이면 return없이 for문 돌며 다음 char체크
if set(s) == set(suffix) :
return char + self.removeDuplicateLetters(suffix.replace(char, ''))
#재귀이므로 이 값이 마지막에 붙어서 나옴. 붙일 게 없으니 빈값으로 함.
#왜 이게 맨 뒤에 붙이서 나오지???? return 하자마자 함수 실행 끝해야 하는 거 아닌가
return ''
2. 스택
-
Get
- 파이썬 집합 자료형 set
- set(...) 으로 생성
- 중복제거
- string.index(char) : 문자열에서 특정 문자의 인덱스 찾기. char말고 string을 넣어도 가능함
- string.find(...) : index()와 거의 같은 기능을 함.
- index()와 find()의 차이는 찾는 값이 존재하지 않을 때
- index : ValueError 에러 뱉음. try-catch문으로 감싸서 사용할 것
- find : -1 을 반환함
반응형
'DSA > Algorithm' 카테고리의 다른 글
[LeetCode 622] Design Circular Queue (0) | 2022.09.27 |
---|---|
[LeetCode 225] Implement Stack using Queues (0) | 2022.09.27 |
[LeetCode 19] Reverse Linked List II (0) | 2022.09.26 |
[LeetCode 42] Trapping Rain Water (1) | 2022.09.20 |
[백준 9372] 상근이의 여행 Python 트리 tree (0) | 2021.10.04 |