438. Find All Anagrams in a String - Trial 2

#HashTable #String #SlidingWindow

 

두 문자열 s와 p가 주어진다. 이 때 p의 모든 문자가 사용된 s의 시작 인덱스를 리스트로 반환한다.

단, 반환하는 리스트 안의 요소 순서는 상관이 없다.

 

* 애너그램(Anagram)이란?

단어나 구의 글자를 재배치하여 만든 단어나 구문으로, 모든 글자를 한 번씩만 사용한다.

 

예시:

(Input) s = "cbaebabacd", p = "abc"
(Output) [0,6]

 

---

Trial 2 : Python3, 22/02/03

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        result = []
        phash = defaultdict(int)
        shash = defaultdict(int)
        
        for char in p:
            phash[char] += 1
            
        for idx, char in enumerate(s):
            shash[char] += 1
            
            # 누적된 문자 앞에서부터 하나씩 제거하기
            if idx >= len(p):
                delchar = s[idx-len(p)]
                if shash[delchar] > 1:
                    shash[delchar] -= 1
                elif shash[delchar] == 1:
                    del shash[delchar]
            
            if phash == shash:
                result.append(idx + 1 - len(p))
                
        return result

 

풀이:

이전에 풀이에 사용해봐야겠다고 한 HashTable(이하 HT) 기능과 Sliding Window 알고리즘을 사용했다.

* Sliding Window 알고리즘:

일정 범위의 배열을 탐색하거나 비교할 때 중복되는 범위를 재사용한다.

먼저 p 문자열의 HT를 생성한다. (비교할 기본적인 데이터 구축)

참고로 defaultdict(int)을 사용하면 자동으로 값을 0으로 채워주기 때문에 별도로 초기화 할 필요가 없다.

 

다음으로 s 문자열 내에서 한 문자씩 탐색하면서 새로운 값을 추가하고 오래된 값을 삭제해주면 되는데,

이 때 for 반복문에서 사용하는 enumerate(자료형) 함수는 순서가 있는 자료형을 받아서 인덱스와 값을 함께 반환한다.

즉, 위의 코드의 경우 s 문자열을 입력값으로 주었으므로 s[idx] == char 를 만족한다.

 

s 문자열의 HT에 차례대로 하나씩 추가하다가 인덱스가 p 문자열의 크기와 같아진 이후부터는

가장 오래된 값을 하나씩 삭제해주어야 한다. 

따라서 지워야 할 문자를 delchar 변수에 저장하고 sHT 에서 해당 문자의 개수가 1보다 큰 경우에는 1을 빼주고,

개수가 1인 경우에는 해당 요소 자체를 삭제한다.

요소 자체를 삭제하는 이유는 pHT 와 비교할 때 요소가 남아있으면 제대로 비교가 이뤄지지 않기 때문이다.

 

이 과정을 거친 후에 pHT 와 sHT 를 비교해서 두 딕셔너리가 같다면 가장 처음의 인덱스를 추가한다.

(현재 인덱스가 애너그램의 마지막 인덱스를 나타내므로 p 문자열 길이만큼 빼고 1을 더해주어야 한다.)

 

 

리뷰: 

런타임은 88.17%, 메모리는 77.56% 의 결과를 얻었다.

첫 시도에서는 카테고리와 상관없이 떠오르는 방법대로 풀어서

간단한 경우는 해결했지만 주어진 문자열이 복잡한 경우에는 타임리밋에 걸렸다.

두 번째에는 카테고리를 유념하면서 사용해야 할 도구(HashTable)와 관련된 알고리즘 기법(Sliding Window)을 참고해서 풀었고 첫 번째보다 훨씬 일반적인 해결법을 얻을 수 있었다.

잊고 있던 알고리즘을 다시 찾아보고 해결법에 적용하면서

알고리즘 문제들을 푸는 의미를 다시 생각해 볼 수 있는 기회였다.