문제 설명

https://www.hackerrank.com/challenges/hackerrank-in-a-string/problem

시도

최초로 목표로 하는 글자를 찾은 다음에는 최초 목표 글자의 다음 인덱스부터 찾기 시작한다는데서 착안해서 아래와 같이 풀었다.

def hackerrankInString(s):
    chars = [c for c in 'hackerrank']
    result = 'YES'
    
    for c in chars:
        try:
            idx = s.index(c)
            s = s[idx + 1:]
        except ValueError:
            result = 'NO'
    
    return result

그러나 위의 풀이는 지속적으로 string slicing을 수행하므로 시간 복잡도의 측면에서 그다지 좋지 않다. string slicing은 수행시간이 O(n^2)인 작업 이기 때문이다.

해결

이럴 경우 지속적으로 문자열을 복사하기보다 스택을 활용하는 것이 더 낫다.

def hackerrankInString(s):
    # reverse string
    stack = [c for c in 'hackerrank'[::-1]]
    
    """
    ex) 
    hhhaacckerrrank
    스택: knarrekcah (hackerrank를 뒤집은 배열)
    
    마지막에서부터 찾아나가기 시작한다.
    1. h를 찾았으므로 스택에서 h를 비운다.
    2. a를 찾았으므로 스택에서 a를 비운다.
    ...
    """
    for c in s:
        if stack and c == stack[-1]:
            stack.pop()
            
    return 'NO' if stack else 'YES'

스택을 사용할 경우의 시간 복잡도는 O(n)으로 전보다 개선되었음을 알 수 있다.