[코테/네카라] 단어 찾기 (KMP 아님)

코테의 실력은 경험에서 나온다.
3번 문제 였지만 도전적으로 보여서 두 번째로 시작했는데, 접근이 틀려서 결론적으로 코테를 망가트린 주범이었다. 후회한다.

결론

신중하지 못하게 KMP 응용문제로 파악했고 잘 못 접근하여 1시간 30분 소모하고 못 풀게 됨. 문제의 제약 조건을 자세히 읽었다면 훨씬 빠르고 쉬운 접근 방식으로 문제를 풀었을지도.

문제

보안을 위해서 변형해서 기록

• 각 문장에 주어진 단어 또는 구(?)가 등장하는지를 확인 하는 문제. 단어는 한 단어 일 수도 있고, 붙어 있지 않는 두 단어 이상의 길이의 구(?) 일 수도 있다. 즉 "I love you" 가 문장이라면 "I you"라는 쿼리는 True를 return 해야 한다. "I love you I like you" 라면 True True로 두번 Return 해야 한다.

접근

나는 지난 주에 코테를 보고 KMP 패턴 찾기 문제를 틀렸다. 그 문제를 복기하다가 오늘 이 문제가 나왔길래 KMP 패턴 찾기로 접근한 것이다. 그러나.. 치명적인 오류가 있었다. "She likes me" 문장에서 "like" 쿼리는 False를 반환해야 하는데, KMP 에서는 True를 반환하게 된 것이다. 이 사실을 문제 마지막까지 인지 하지 못했고, 그에 더해서 KMP로는 "me She"와 같은 뒤집어진 패턴이나 "She me"를 파악하기도 어렵다.

복기

구글링과 ChatGPT를 가지고 KMP를 혼자 변형하려고 애를 쓰다보니 시간이 모두 지나갔고 상대적으로 쉬운 4번을 못풀게 되었다. 아쉬운 부분. 다시 생각해보니 문자을 split() 하고 list 로 만든 후에 요소가 있는지를 확인하는 간단한 방식으로 접근했으면 되지 않았을까 생각도 해본다.