알고리즘 시작 - 가사 검색

시작하며

카카오 문제가 스토리도 있고 재밌는거 같아서 파기 넘치게 도전했다.

문제

https://programmers.co.kr/learn/courses/30/lessons/60060

내 풀이

내가 생각한 풀이

• 정렬한다. (fro로 시작하는 오름차순. 만일 a,b 모두 fro로 시작한다면 문자열 길이순 오름차순 )
• 이분탐색을 이용하여 조건을 만족( fro로 시작 && 문자열 길이 일치 )하는 최초의 문자열 발견하면 문자열 기준으로 뒤와 앞을 돌면서 조건 만족하는 문자열의 시작과 끝 지점 찾기
  ( end Index - start Index + 1)개

결과적으로 기본 예제 테스트만 통과하고 낙방.

일단 정확성 테스트는 아래처럼 쉽게 생각해서 플 수 있다.

https://rok93.tistory.com/m/entry/프로그래머스-가사-검색-2020-KAKAO-BLIND-RECRUITMENT-문제-4번

내 목표는 정확성 테스트 통과였는데 너무 어렵게 생각한 것 같다.

그리고 효율성 테스트를 통과하기 위해서는 ‘트라이’라는 자료구조를 써야한다고 한다.

마치며

처음부터 해설을 보고 ‘이분탐색’ 문제로 생각해서 그런지 굉장히 어렵게 생각했다. 실제로 난이도도 높은 문제였고. 이제부터는 레벨 2정도 난이도의 문제를 풀기로 했다.
이번주는 알고리즘 공부를 시작했다는 것에 의의를 두는 것으로 ^^
다음주는 이변이 없다면 스택 문제를 풀 예정이다.