[HackerRank] Hackerrank In String

leejh3224·2018년 12월 5일
1
post-thumbnail

문제 설명

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)으로 전보다 개선되었음을 알 수 있다.

profile
다양한 것들을 시도합니다

2개의 댓글

comment-user-thumbnail
2018년 12월 6일

알고리즘 연습하기 좋은 곳 같아요 감사합니다!

접속해서 같은 문제를 풀어보았는데
이미 풀이를 보고 가서 그런지 이 방법밖에 떠오르지가 않네요 ㅎㅎ

1개의 답글