ch9-2(leetcode 316). 중복 문자 제거

룰루루 2023. 1. 10. 21:40

2023. 1. 10. 21:40

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

재귀함수를 이용할 수 있다.

중복 문자를 제거해서 알파벳 순서(lexicographical order)가 가장 빠르려면, 알파벳에서 앞에 오는 문자는 앞에, 뒤에 오는 문자는 뒤에 있어야 한다(당연).

set() 함수를 사용하면 문자열이나 리스트의 원소들 중 중복을 제거해서 지정된 순서 없이 리턴한다.

이후 sorted() 함수를 리스트에 사용하면 리스트의 원소들을 알파벳 순서에 맞게 정렬할 수 있다.

for char in set(sorted(s)):

해당 풀이에서는 조건에 맞는 문자열을 하나씩 뒤에다가 붙여서 결과값을 리턴하는 방식으로 진행한다.

즉 i번째 단계에서 계산 중인 정답 문자열에다가 새 문자열을 이어 붙인다고 해 보자.

이어 붙이려는 문자열은 자신의 앞에만 포함되어 있는 다른 문자열이 있으면 안 된다.

예를 들어 acbefjgk 라는 문자열에서 a 다음에 b라는 문자열을 이어 붙일 수는 없다. 왜냐하면 a와 b 사이에는 c라는 문자열이 있고, c는 b 다음에는 한 번도 등장하지 않으므로 반드시 a와 b 사이에 등장해야 하기 때문이다.

이를 확인하려면 문자열 char의 앞에 있는 문자열이 문자열 char의 뒤에도 등장하는지를 확인해야 한다.

index() 함수를 사용해서 전체 문자열 중 char이 등장하는 첫 번째 인덱스를 알아낼 수 있다.

이후 문자열 슬라이싱을 사용해서 해당 인덱스 이후의 문자열을 따로 슬라이싱한 뒤, set()을 사용하면 중복에 상관 없이 어떤 문자열이 등장하는지를 알 수 있다.

suffix = s[s.index(char):]	# suffix of char
if set(s) == set(suffix):	
	# do something
	return thisfunction(strs.replace(char, "")

만약 문자열 char의 앞에 있는 모든 문자열이 문자열 char의 뒤에도 등장한다면, 어차피 for loop는 알파벳의 정렬된 순서대로 진행되므로 해당 문자열 char을 정답 문자열에 추가할 수 있다.

다만 문자열 char이 정답 문자열에 포함되었으므로, 재귀함수를 사용해서 계산될 파라미터 문자열에서는 char 문자열을 모두 공백으로 바꿔 주어야 하겠다. replace() 함수로 간단하게 처리할 수 있다.

string.replace(대체될 문자열 A, 대체할 문자열 B) : string 안에 있는 문자열 A를 문자열 B로 바꾼다.

스택을 이용해서 풀 수 있다.

기본적으로는 주어지는 문자열들을 스택에 쌓다가, 특정 조건에 해당하면 스택의 문자열들을 제거한다. 재귀함수와 방식은 유사하고 사용하는 자료형이 다르다고 볼 수 있다.

이외에도 Counter 자료형을 이용해서, 주어진 문자열에 각 문자가 몇 번 등장하는지를 기록 후 사용한다.

counter = collections.Counter(s)

또한 set 자료형을 사용해서, 이미 계산을 마친 문자열은 해당 집합에 추가해서 이후 같은 문자열이 나올 경우 계산하지 않고 다음 loop로 넘어간다(continue).

스택의 문자열을 제거하는 필수 조건도 앞의 재귀 함수와 비슷하다.

스택에 문자열이 남아 있고, 새로 추가되는 문자열이 스택의 맨 위 문자열보다 알파벳 순서가 빠르고, 스택의 맨 위 문자열이 이 이후에도 등장한다는 조건이 충족되면, 스택과 set에서 문자열을 제거한다.

while stack and stack[-1] > char and counter[stack[-1]] > 0:
	sets.remove(stack.pop())

최종적으로 스택에 남은 문자열이 정답이 된다.

리스트 자료형을 문자열로 변경하기 위해서 공백 문자열을 기준으로 join() 메소드를 사용하면 간단히 바꿀 수 있다.

return "".join(stack)

아스