Rotation point 찾기 문제(ft. Binary Search)

Rotation point 찾기 문제

문제

a부터 z 순으로 적혀진 사전을 읽다가 모르는 단어가 나오면 단어장에 기입하는 작업을 하려고 한다. 단, 사전의 어느 중간부터 펴서 이 작업을 시작한다. 그래서 뒤로 가면서 이 작업을 수행하다가 사전의 끝에 도달하면 사전의 처음부터 시작해서 처음에 폈던 페이지 전까지 이 작업을 한다.

이 모르는 단어는 배열에 순서대로 저장하여, 예시를 들면 다음과 같은 형태가 된다.

['ptolemaic','retrograde', 'supplant', 'xenoepist', 'asymtote', 'babka']

알파벳 오름차순으로 진행되다가 사전의 끝까지 찾고 나면 다시 앞에서부터 시작하기 때문에 어느 순간 내림차순이 됐다가, 그 다음 다시 오름차순이다. 위 예시에서는 asymotote 라는 단어가 그 포인트이며, 이렇게 어느 순간 내림차순이 됐다가 다시 오름차순으로 시작하는 이 포인트를 Rotation point라고 하자. 이 Rotation point를 찾는 알고리즘을 구현하라.

 

힌트

Binary Search

 

문제의 포인트

Rotation point가 특정 원소의 왼쪽에 있을지, 오른쪽에 있을지를 어떻게 알 수 있는가. 전형적인 바이너리 서치에서 특정 숫자가 어디에 있는지를 찾을 때에는 중간 인덱스의 원소와 비교한 다음 왼쪽인지 오른쪽인지 범위를 좁힌다. 여기에서는 무엇과 비교를 해야 Rotation Point가 왼쪽인지 오른쪽인지 알 수 있을까?

 

풀이

def find_rotation_point(words):
    first_word = words[0] 
    start = 0
    end = len(words)-1
    
    while start <= end:
        mid = (start + end) // 2
        # Rotation point인지 
        if words[mid] - words[mid-1] < 0:
            return mid
        # 로테이션 포인트가 오른쪽일 때
        if words[mid] > first_word:
            start = mid+1
        # 로테이션 포인트가 왼쪽일 때
        else:
            end = mid-1      

• 코드 구현할 때 내가 한 실수

  1. 처음에 mid = (start + end) / 2 라고 썼다. 그냥 나누기 부호를 써서 mid가 float형이 되어버리는 바람에 에러가 났다. 기초적인 부분이지만 조심하자.

  2. while문을 처음에 작성할 때 start < end 라고 써서 아무 것도 리턴되지 않는 경우 발생. 그러니까 start = end인 경우를 간과하고 탈출 조건을 잘못 작성했다. 코드상으로는 매우 작은 차이처럼 보이지만 루프 탈출문은 중요하므로 주의하기.

      

• 코드 구현하기 전에 틀린 부분

  처음에 힌트를 보지 않고 문제를 풀었을 때는 O(n)이라고 풀었다. 일단 정렬됐긴 한데, 일부만 정렬되어 있으니까 바이너리 서치를 쓰지 못할 거라고 패스했고(정말 전형적인 케이스만 생각한...), 그 다음에 생각난 것은 Rotation Point는 배열 원소 중 최소값일테니까, 선택 정렬에서 사용하는 방식으로 최소값을 찾으면 되겠다고 생각했다. 단 한번만 찾으면 되니까 O(n)이겠다 생각했는데, 정답은 O(logN)이었다.