문제 설명

https://www.hackerrank.com/challenges/two-characters/problem

시도

다이내믹 프로그래밍 문제라는 생각이 들어서 dp 배열을 만들어서 어떻게 해볼까 생각했지만 "Alternating"(abab와 같이 서로 교차하면서 바뀌는 문자열)을 어떻게 파악할 수 있을지가 감이 오지 않았다.

Discussions를 들어가서 코멘트를 쭉 읽어보니 Regex를 썼다는 사람도 있고, 26x26 행렬(a-z, a-z)을 만들어서 풀었다는 사람도 있었다.

통과

그 중 가장 짧고, 이해하기 쉬웠던 방법을 공유할까 한다.

먼저 코드부터 살펴보자.

from itertools import combinations

def alternate(s):
  	# 예외처리: 길이가 1이면 0을 리턴 
    if len(s) == 1:
        return 0
      
    unique = set(s)
    
    # 가장 긴 alternating 문자열의 길이
    longest = 0
    
    # 파이썬은 c++의 STL처럼 조합/순열을 지원한다.
    # combinations(counter, 2)의 경우 counter의 key에서 2개의 문자로 이뤄진 조합을 돌려준다.
    # abc -> (a,b), (a,c), (b,c)
    for pair in combinations(unique, 2):
      	# 조합 안의 두 글자에 글자에 해당하는 글자만 찾는다.
        matches = [c for c in s if c in pair]
        
        # zip(matches, matches[1:])는 matches를 두 글자씩 묶은 리스트 튜플을 돌려준다.
        # abae -> (a,b), (b,a), (a,e)
        # 그리고 모든 경우에 각 튜플의 두 글자 c1,c2가 서로 다르다면 alternating한다고 볼 수 있다.
        if all(c1 != c2 for c1, c2 in zip(matches, matches[1:])):
            longest = max(longest, len(matches))
    
    return longest

알고리즘 문제를 풀 때 파이썬의 장점은 생각해내려고하면 꽤 복잡할 수 있는 것들이 내장 라이브러리를 통해 지원된다는 점이다.

itertools 안에 있는 combinations나 permutaion도 그 예 중 하나다.

만약 combinations를 사용하지 않는다면 직접 조합이 가능한 경우를 찾아야한다.

그 이후에는 그 조합이 alternating하는 지를 가려내기 위해서 조합 안에 있는 글자만 찾는다. (matches)

그리고 matches를 두 글자 단위로 잘라서 그 두 글자가 서로 다른지를 검사한다. (alternating한 지를 검사하는 부분)

만약 그렇다면 longest의 크기를 업데이트해준다.

교훈

일단 쉬운 문제는 아니었다. 그리고 새삼 문제를 잘 읽어야한다는 사실을 깨달은게 문제를 자세히 읽으면 '두 글자'이면서 'alternating'하는 문자열을 찾는게 핵심이기 때문이다. 문제의 정의를 이해하는데 너무 많은 시간을 낭비했다.

그리고 이번 문제를 통해 유용한 라이브러리인 itertools를 알게 됐다.
내장 라이브러리를 다양하게 사용하면 직접 구현할 때보다 실수가 줄고 더 적은 코드로 더 이해하기 쉽고 읽기 좋은 코드를 짤 수 있다. 되도록 폭 넓게 이용해야겠다.