반응형

 백준에서 lower_bound, upper_bound는 정렬된 배열에서 상당히 많이 썼습니다. 파이썬에는 없을까요?

 


 bisect 모듈에는 bisect_right와, bisect_left가 있습니다. 쉽게 말해서 이 둘은 정렬된 list에서 upper_bound와 lower_bound에 대응되는데요. 어떻게 동작하는지 보겠습니다. 키가 정수인 경우에 대해서 생각해 보겠습니다.

 

 

 먼저, 전자부터 보겠습니다. 일단 lo와 hi는 탐색 범위를 의미합니다. 배열 전체를 탐색하려는 경우에는 a와 x를 넣습니다. 여기서 a는 list이고 x는 기준 값을 의미해요. 여기서, 우리는 어떻게 범위를 좁히는지 볼 필요가 있는데요. a[mid]보다 x가 작으면 hi가 mid가 됩니다. 즉, 찾으려는 수 보다 a[mid]가 큰 상황입니다.

 

 

 그래서, 이 경우에는 hi를 mid로 바꿉니다. 즉, 탐색 범위가 [lo, hi]였던 것이 [lo, mid]가 됩니다. 그런데, 왜 이런 경우에 [lo, mid]로 바꿔야 할까요? [lo, mid-1]로 바꾸면 안 될까요?

 

 

 만약에 [lo, mid-1]로 바꾸면 이런 반례에 걸리게 됩니다. 만약에 a[mid] 값이 x보다 작거나 같다면 어떨까요?

 

 

 그러면 탐색 범위를 [mid+1, hi]로 바꾸면 됩니다. 34번째 줄이 그러한 역할을 합니다.

 


 

 bisect_left는 어떨까요? 탐색 범위를 어떻게 좁힐까가 문제인데요. a[mid]가 x보다 작다면, 왼쪽 부분을 탐색할 필요가 없습니다.

 

 

 그런가요? [le, mid]를 탐색해 봤자, x보다 크거나 같은 구간이 없기 때문입니다. 그렇지 않으면, hi를 mid로 잡는데요.

 

 

 이것은 mid가 x보다 크거나 같을 때도 그리 잡는다는 것을 알 수 있습니다. 구간을 조건에 따라서 좁혀가는 구나. 정도만 생각하시면 크게 어렵지 않습니다. 그리고 주석 부분을 잘 보면 __lt__가 있습니다.

 

 

 이는 <와 대응됩니다. less than. 이걸 구현하면, 정렬도 할 수 있고, 그것을 바탕으로 이진 탐색을 할 수 있다는 이야기도 됩니다.

 

 


 간단한 예제를 하나 보겠습니다. 나오는 문자열의 길이가 최대 10이고, 소문자로만 이루어져 있다고 합시다. 리스트에 나오는 접두사가 gt인 것의 갯수를 찾아야 한다고 해 보겠습니다. 어떻게 하면 될까요? 일단 나오는 문자열의 길이가 최대 10이다. 라는 것에 밑줄을 쳐야 합니다. 왜 이게 중요한지는 코테를 대비하신다면 깊게 생각해 보시는 것도 도움이 될 듯 싶습니다. 사실, 문자열 문제는 쿼리에 들어가는 문자열 길이의 합이 x 이하이다. 이거나, 문자열 길이가 y 이하이다. 라는 조건이 왕왕 등장하는데요. 이 조건이 뭘 의미하는지 깊게 고민해 보시는 것도 도움이 될 듯 싶어요.

 

 

 bisect_left와 bisect_right를 이용하면 쉽게 해결할 수 있습니다. 먼저 'gt'보다 크거나 같은 최초의 위치를 찾습니다. 6번째 줄에서 그렇게 하고 있습니다. 다음에, 7번째 줄에 'gt{'가 있는데요. 'gt어쩌고'는 사실 'gt{'보다 클 수는 없습니다. 왜냐하면 'gt'에서 무엇인가 append가 될 때 소문자나 대문자만 추가될 텐데, 최악의 경우에 'gtzzzzzzzz'가 될 것이거든요. 그래서, 이거보다 큰 최초의 위치를 찾아도 됩니다.

 

 그런데, 사실 더 간단한 방법은 'gt{'보다 큰 최초의 위치를 찾는 것입니다. 'gtzzzzzzzz'보다 'gt{'가 크기 때문이죠. 즉, 'gtz..z' < 'gt{'입니다. 이는 'z'보다 '{'이 더 크기 때문입니다.

 

 

 실행 결과는 위와 같고, 'gt'를 접두어로 가지는 것은 5에서 1을 뺀 4임을 알 수 있습니다. 시간 복잡도는 n이 배열 크기일 때, 쿼리당 O(10logn)입니다. 만약에 '{'가 임의의 소문자보다 뒤에 나온다는 걸 몰랐다면 어떻게 해야 할까요? 이 때는 chr을 이용하면 됩니다. 이 글을 참고하시면 어떤 건지 알 수 있을 듯 싶습니다. 아래 코드는 아스키 코드 번호가 x인 문자를 구하는 프로그램입니다.

 

 

 for loop를 돌면서 처리하고 있습니다.

 

 

 결과는 위와 같고, z보다 뒤에 있는 것은{, |, }, ~임을 알 수 있습니다.

 

반응형

댓글을 달아 주세요