Toy 문제 14

문제

부분적으로 오름차순 정렬*된 정수의 배열(rotated)과 정수(target)를 입력받아 target의 인덱스를 리턴해야 합니다.

 

주의사항

• rotated에 중복된 요소는 없습니다.
• target이 없는 경우, -1을 리턴해야 합니다.

Advanced

• 단순히 처음부터 끝까지 찾아보는 방법(O(N)) 대신 다른 방법(O(logN))을 탐구해 보세요.

 

수도코드(해석)

 

삽입정렬 : 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. 배열이 길어질수록 효율이 떨어집니다.

 

이 문제가 가장 원하는 점은 sort 메서드를 사용하지 않고 해당 인자가 몇번째에 위치하는지 구해야 합니다.

 

절반이 각각 오름차순으로 정렬되어 있기 때문에

좌측의 시작과 끝

우측의 시작과 끝인 부분을 구해서

target이 어느 부분에 들어가는지 중앙을 포인트 지점을 정해서 비교를 통해 확인을 하고

target이 해당 부분에 포함 된다면 포인트 되는 부분을 이동시켜 확인을 해보면 됩니다.

좌측에 해당할 경우 중앙 포인트를 -1칸 이동, 우측에 해당할 경우 포인트를 +1칸 이동하면 됩니다.

 

이렇게 찾을 경우 어드벤스드에 해당이 되기 때문에 처음부터 다 찾는것 보다 절반을 나눠 찾기 때문에

코드의 효율이 증가한 것은 맞습니다. 제 생각에는 시간복잡도는 O(N)과 O(logN) 사이가 아닌가 싶습니다.

 

코드

const rotatedArraySearch = function (rotated, target) {
  // TODO : 여기에 코드를 작성합니다.
  let start = 0;
  let end = rotated.length - 1;
  let mid = 0;
  
  while(start <= end){
    mid = Math.floor((start + end) / 2)

    if(rotated[mid] === target){
      return mid;
    }

    if(rotated[start] <= rotated[mid]){ //왼쪽측에
      if(rotated[start] <= target && target <= rotated[mid]){ // 범위가 맞으면
        end = mid-1; // -1
      }else{
        start = mid+1; //아니면 +1로 우측으로 보낼수 있겠함
      }
    }else{ //오른쪽
      if(rotated[mid] <= target && target <= rotated[end]){ // 범위가 맞으면
        start = mid+1; // +1칸 이동시켜주고
      }else{
        end = mid-1; // 아닌 경우 좌측으로 밀어야 되기 때문에 -1
      }
    }

  }
  return -1;
};