[240211] 알고리즘 리부트 3일차 - 백준 1543 자바

[Part1-Chapter01-Clip05]

 

- 백준 1153 문서검색

 

 

 

 

 

첫번째 풀이는 String의 패키지의 replace 메서드를 이용해 해당하는 타겟 단어가 존재하는 경우 영문자가 아닌 기호로 변경하고 그 기호 수를 세어 타겟 수를 반환했다. 가장 단순하게 풀 수 있는 방법이었다. 이렇게 풀고 말기에는 아쉬워 투포인터 방식으로 타겟 단어 탐색을 진행했다. 주의해야 할 점은 단어 탐색이 처음부터 틀렸을 때, 중간부터 틀렸을 때 어디서 부터 탐색을 다시하게끔 조정하냐는 것이었다. 생각하지 못한 테케가 왕왕 있어서 구현에는 조금 시간이 걸렸다.

 

아래 케이스가 오답을 잡아준 케이스였다.

ababaa

abaa

이 경우  aba까지 일치하고 그다음 a에서 틀리는 경우

시작점을 틀린 인덱스가 아닌 두번째 글자부터 다시 탐색하도록 구현해야 했다.

다른 방식은 다음과 같다. 왼쪽은 String 패키지의 indexOf 메서드를 활용한 풀이이고, 오른쪽 풀이는 이중 반복문을 활용하여 두개의 인덱스를 조합하여 단어를 찾는 방식이다. 이 때 (i+j)를 첫 풀이 때 떠올렸다면 보다 간단하게 풀 수 있었을 것 같은데 많이 아쉽다. 아직도 인덱스를 활용하는데 익숙하지 않아 씁쓸하다. 이 풀이에서 주의할 점은 인덱스의 합이 문서의 길이를 넘지 않도록 하는 것과 단어를 찾았을 때, 단어 길이 이후를 지정할 때 반복문 내에서 i 가 하나씩 증가됨을 고려하여 -1처리를 해주는 것이다. 한 문제로도 이렇게 다양한 풀이를 할 수 있다니 확실히 조건문을 복잡하게 걸수록 실수가 많아지는 것을 한 번 더 경험한 문제다.