반응형

 이번 시간에는 Longest Substring Without Repeating Characters 문제를 풀어보면서, 어떻게 시간 복잡도를 분석하는지 보도록 하겠습니다. 이 문제는 길이가 5만 이하인 문자열에서, 문자가 반복되지 않는 가장 긴 부분 문자열을 찾는 문제입니다. 문자열에 들어갈 수 있는 문자는 알파벳, 숫자, symbol, 그리고 space 문자입니다.

 

 보통, 이렇게 주기 보다는 CodePoint는 아스키 코드 범위 내에 있다. 혹은 유니코드 범위 내에 있다. 이런 전제를 까는 게 더 좋기는 한데 넘어가 봅시다. 이모지 같은 것들 때문에 태클이 들어올 여지가 있습니다. 저 또한 문제 제작했을 때 간과했던 부분이기도 합니다.

 


  문자열에 들어갈 수 있는 문자 집합이 작을 때에는 어떨까요? 놀랍게도 브루트 포스 풀이가 통과합니다. 아래 코드를 보겠습니다.

 

 8번째 줄에 걸린 for 문은 시작점을 i로 잡습니다. i번째 위치에서 시작하는 부분 문자열 중에, 문자가 2번 이상 겹치지 않는 최장 길이를 구하는 메소드는 chk입니다.

 

 

 chk 메서드를 보시면, lo에서부터 문자열의 끝까지 탐색해 보게 됩니다. 그래서, 조건을 만족하지 않는 위치가 나오는 순간 바로 종료해 버립니다. 이 메서드는 겉으로만 보면, 최악의 경우에 O(|s|)일 거 같습니다. 그런데, 문자열에 들어갈 수 있는 문자셋이 크지 않다면, O(|s|)만큼 돌지 않습니다. 왜일까요?

 

 비둘기 집의 원리 때문입니다. 예를 들어서, 문자열에 들어갈 수 있는 문자 셋이 'a', 'b', 'c'라고 해 봅시다. 문자열의 길이가 4이면 어떻게 될까요?

 

 

 문자 셋의 크기는 들어갈 수 있는 방의 개수이고, 문자열 길이는 사람 수라고 해 봅시다. 이 경우에, 둘 이상 들어가는 방은 하나 이상 존재하나요? 네. 그렇습니다. 왜냐하면, 1번과 2번, 3번이 3개의 방에 한 명씩 들어간 이후의 상황을 생각해 봅시다.

 

 

 4번은 어느 방을 들어가야 하나요? 아무 방이나 들어간다고 하면, 두 명 이상 있는 방이 존재합니다. 이를 비둘기 집의 원리라고 합니다. 해시테이블과도 관련이 있는 구조인데요. 링크에 자세히 설명해 놓았으니 참고해 보셔도 좋을 듯 하네요. 어찌 되었던, 들어올 수 있는 문자 셋의 크기가 매우 작다고 해 봅시다. 널문자 제외하고 코드 포인트로 1부터 127까지 범위라고 해 봅시다.

 

 그러면, 방의 갯수는 127인 상황입니다.

 

 몇 명 이상이 들어가야 둘 이상이 들어간 방이 최소 하나 이상 나오게 될까요? 128입니다.

 

 

 128번째 사람이 들어갈 때에는 1번부터 127번까지 빈 방에 모두 들어간 상황이 되었기 때문입니다. 따라서, brute force의 경우에도, 꽤 빠르게 동작하게 됩니다. 정확히 말하면 문자셋 집합의 크기를 k라고 하면 O(k|s|)가 됩니다. k가 128이라면, 문자열 s의 길이가 5만인 상황에서도, 5만에 128을 곱한 640만번 compare 연산을 하게 되므로, 시간 내에 동작합니다. 그래서, 슬라이딩 윈도우 풀이는 필요 없습니다.

 

 만약에, 나올 수 있는 문자가 유니코드 범위였으면 어떨까요? 예를 들어 한글이나 한자도 나올 수 있다면? 이 경우에는 k가 매우 커지게 됩니다. 한글만 해도 11176자입니다. 11176에 5만을 곱하기만 해도 5억이 넘어갑니다. 이럴 때에는 슬라이딩 윈도우를 써야 하는 것입니다.

 


 이제 슬라이딩 윈도우 풀이를 보겠습니다.

 

 복잡해 보이는데요. 사실 별 거 없습니다. e를 증가시킬 수 있으면 증가시키고, 그게 아니라면 s를 증가시키면 됩니다. 이게 무슨 소리인지 모르겠으니, 예제를 보도록 하겠습니다.

 

 

 처음에는 아무 것도 없는 상황이에요. 이 때 a를 추가할 수 있어요. 그러므로 포인터 e를 오른쪽으로 이동시켜요.

 

 

 다음에 b를 추가할 수 있나요? 네. a 하나만 있기 때문입니다. 따라서 e를 한 포인트 이동시킵니다.

 

 이제 e가 가리키는 b를 추가할 수 있나요? 아니요. 없습니다. 그러므로 s를 한 칸 이동시킵니다. 그러면 문자 a가 하나 빠질 겁니다. 그러면 e가 가리키는 b를 추가할 수 있나요?

 

 

 그럴 수 없습니다. 왜냐하면, 여전히 b가 하나 있다는 정보가 있기 때문입니다. 따라서 s를 한 칸 이동시키고 문자 b를 하나 뺍니다. 그 다음에는 b를 추가할 수 있나요?

 

 

 네. 그러므로 b를 하나 추가시키고 e를 한 포인트 오른쪽으로 이동시킵니다. 언제 끝내면 될까요?

 

  e가 문자열 끝에 도달했을 때 끝내버리면 됩니다. s <= e여야 하므로, 최악일 때에도 O(2|s|)가 됩니다.

 

[관련글]

비둘기 집의 원리는 무엇일까요?

슬라이딩 윈도우가 무엇일까요?

반응형

댓글을 달아 주세요

  1. Deborah

    알고리즘에 대해서 배우고 가네요.