[HackerRank] Hackerrank In String

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

문제 설명

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

시도

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

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

해결

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

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

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

2개의 댓글

comment-user-thumbnail
2018년 12월 6일

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

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

1개의 답글