문제
- https://www.hackerrank.com/challenges/sherlock-and-anagrams/problem?isFullScreen=true
- Anagram을 간단하게 설명하면, 순서와 상관없이 문자열(1개 포함)의 조합이 2번 이상 존재하는 경우를 찾는 문제이다.
- 문제를 이해하기가 어려웠다. 그만큼 예시를 많이 제공하니 잘 읽어보아야 삽질을 안한다.
아이디어
- 모든 문자열의 조합을 보면서 같은 알파벳 조합으로 구성된 문자열을 count 하면 된다.
- 이를 위해 정렬한 후에 Counter에 문자열을 key 값으로 count 한다.
- 자기 자신은 제외되어야 하니 count가 2 이상인 문자열만 anagram의 조건에 해당하는것이다.
- 알고리즘의 핵심은 Sliding Window 이다.
Sliding Window 예시
- abba 가 있을 때, a, b, ab(for ba), abb(for bba) 이렇게 네개의 문자열이 두 번씩 등장한다.
- 문자열의 역순을 탐색하는 것이 아니다. 조합을 탐색 해야한다.
- 또 다른 예시로 cdcd가 있을 때, c, d, cd(for cd), cd(for dc), dc(for cd)가 두 번씩 등장한다.
Sliding Window 구현
- 맨 앞부터 문자열 1개를 선택하고 오른쪽으로 한 칸씩 이동
- 맨 앞부터 문자열 2개를 선택하고 오른쪽으로 한 칸씩 이동
- 맨 앞부터 문제열 3개를 선택하고 오른쪽으로 한 칸씩 이동
- ...
일단 for loop를 두 개 써야한다는 것까지는 떠올릴 수 있다.
어려운 것는 loop 범위와 slicing 인덱스를 어떻게 설정할 것 인가이다.
- 코드를 보면 이해는 할 수 있지만 혼자서 백지에 구현할 때 막막하다면 일단 외우자
★★★★★
for i in range(1, len(string)):
for j in range(0, len(string)-i+1):
print( s[j:j+i] )- 슬라이딩 윈도우를 구현했으면 이제 정렬을 하고 Counter 객체를 활용해 문자열을 count하면 된다.
- 자신을 제외하기 위해 2번 이상 출현한 문자열들만 필터링하고, total에 더해주면 되는데, 한 가지가 더 있다.
한가지 더
- kkkk의 경우 k가 자신을 제외하고 3번 등장한 것이 아니다.
- 첫번째 k는 3번, 두번째 k는 2번, 세번재 k는 1번 등장했다.
- 따라서 range(n) 함수를 활용해 이들을 숫자에 추가해준다.
전체코드(성공)
total = 0
lst = []
for i in range(1, len(string)):
for j in range(0, len(string)-i+1):
s = ''.join(sorted(string[j:j+i]))
lst.append(s)
c = Counter(lst)
val_lst = []
for val in c.values():
val_lst.append(val)
for val in val_lst:
total += range(val)
print(total)
yozzum