반응형

 String의 indexOf는 어떤 식으로 동작할까요?

 

 

 indexOf를 호출하면, 내부에서, 인자를 7개를 받는 함수가 호출이 되는데요. 1번째 source는 어떠한 문자열에서 찾을 것인지, target은 패턴을 의미합니다. 예를 들어서, "abababb"에서 "ab"를 찾는다고 한다면, "abababb"는 source가 되고, target은 "ab"가 됩니다.

 

 

 fromIndex는, string의 어느 위치부터 탐색을 할 것인지에 대한 정보를 담고 있는데요. 예를 들어서 string이 "abcde"라고 하고, 1번째 위치부터 탐색한다면 fromIndex는 1이 됩니다.

 

 


 아래 코드들을 봅시다.

 

 

 뭔가 조금 복잡해 보이는데요. fromindex가, string에서 어느 위치부터 탐색을 시작할 것인지를 나타냅니다. 먼저 source count는, string의 길이, target count는 패턴의 길이를 의미하는데요. 먼저, from index가 source count보다 큰 경우 부터 생각해 봅시다.

 

 예를 들어 string이 "abcde"라고 해 봅시다. 이 때, 5번째 위치부터 탐색하는 상황입니다. 혹은 6번째 위치나. 이 경우, 문자열의 끝부터 탐색하게 되는데요. target count가 0이라는 것은 빈 문자열이라는 것입니다. 만약에 ""를 문자열의 끝부터 찾는다면, 패턴이 있을 겁니다. 문자열 끝에. 그러니, string의 길이인, source count를 리턴합니다. 그렇지만, tc가 0이 아닌 경우, "a", "b", "df"와 같이, 빈 문자열이 아닙니다. 이 때는 -1을 리턴합니다. 그러면 1762번째 if문은 왜 있을까요?

 

 

 fi의 값이 1이라고 해 봅시다. 그러면 str의 1번째 요소부터 탐색을 할 건데요. tc가 0이라는 것은 패턴이 빈 문자열이라는 겁니다. 그러면 이 때, 시작 위치인 fi의 값을 리턴할 겁니다.

 

 


 그 다음에 java의 indexOf 함수가 어떻게 돌아가는지 봅시다.

 

 

 먼저 first에, target[targetOffset]을 넣습니다. 예를 들어서 targetOffset의 값이 0이라고 해 봅시다. 그리고 패턴이 "ab"라고 한다면, first에는 'a'가 들어갈 겁니다. 다음에 max 값이 문제인데요.

 

 

 탐색 시작 위치를 source_offset부터 잡는다고 해 봅시다. 그러면, i + target_count가 source_count보다 작거나 같을 때 까지 돌리면 되는데요. 그러면, i가 source_count - target_count가 될 때 까지 돌리면 될 건데, 왜 하필 max 값이 이게 아니고, source_offset에 sc - tc의 값을 더한 값을 넣을까요?

 

 


 이런 가설을 세워 봅시다. source count랑, target count가 실제로, 검사 대상의 문자열 길이랑, pattern의 문자열 길이다. 예를 들자면, source_offset이 1이고, target_offset이 1인 경우에, 이 두 값은 각각 5, 4입니다. 연두색으로 칠한 길이가 5, 보라색으로 칠한 길이가 4이기 때문입니다.

 

 

 그러한 경우, 실제로 기준 위치부터, source_offset의 값에, source의 길이 - target의 길이를 더한 위치까지 검사를 하면 될 겁니다. 그 이상으로 커지면, 검사를 안 해도 될 거고요. 그러면, 검색 대상이 되는, 문자열을 기준으로 봐 봅시다.

 

 

 

 이 때, fromIndex의 값이 1이라면 초록색으로 칠한 문자열을 보았을 때, "badua"의 1번째 문자는 'a'입니다. 노란색으로 칠한 부분입니다. 따라서, 노란색으로 색칠이 된 위치부터 탐색을 한다는 겁니다. 헷갈립니다. 그러면 while loop 내부를 봅시다.

 

 


 1769번째 줄을 보면, 계속 i가 증가하게끔 되어 있음을 알 수 있어요.

 

 그런데, 1771번째 줄의 while문을 보면, source[i]가 first하고 같지 않으면 계속 i값을 증가시킴을 볼 수 있어요. 그런데 왜 1769번째의 for문에서 i++이 필요할까요? 그 이유는 첫 글자가 같고, 쭉 탐색했는데, 패턴이 일치하지 않는 경우에, i값을 증가시키기 위함입니다. 그러면 첫 문자가 같은 경우를 봅시다.

 

 

 이 때, targetCount-1회 만큼 for문을 돈다는 것을 알 수 있는데요. 한 눈에 봐도, 첫 글자가 같을 때, 그 위치로부터 탐색했을 때, 패턴이 나오는지 검사하는 부분입니다. 주목해야 할 사실은, 1778번째 줄을 보면 알 수 있듯, end의 값이 j의 값보다, targetCount-1만큼 크다는 것인데요.

 

 

 

 데이터가 이런 식으로 들어온 경우, 최악의 경우, 패턴의 길이에 검색 대상이 되는 문자열의 길이를 곱한 만큼의 비교 연산을 함을 알 수 있어요. 대략적으로. 그러면 언제 써야 할까요? pat이 str의 접미사인지 검사하기 위해서 indexOf를 써야 할까요?

 

 아닙니다. 위에서 언급한 쿼리는 indexOf보다 startsWith로 빠르게 판단할 수 있습니다. indexOf는 str 안에서 pat을 찾을 수 있는지 검사하기 위해서 써야 합니다.

 

반응형

댓글을 달아 주세요

  1. 허니듀크

    태풍올라온다는데 그래서 그런지 너무 후덥지근하네요.
    비많이 온다던데 조심하세요

  2. 상식체온

    오늘도 꾸준 글을 올리셨네요.
    날씨 때문인지 저는 오늘 글쓰는데 머리가 잘 안 돌아가네요.

    아직 도입도 쓰지 못했는데 빨리 써야겠습니다.

    좋은 하루 마무리 하시길 바랍니다.

  3. 곰곰지영

    잘 보고 가요오~ :)