[자료구조/알고리즘] 211027 rotatedArraySearch #while문 #이진탐색변형

📌 rotatedArraySearch

부분적으로 정렬된 배열(rotated)과 정수(target)가 있다. 배열을 조회하여 target의 인덱스를 찾아내는 문제이다. 부분적으로 정렬되었다 함은 배열을 왼쪽 혹은 오른쪽으로 0칸 이상 순환 이동할 경우 완전히 정렬되는 배열이다.

ex) [4, 5, 6, 0, 1, 2, 3]은 왼쪽으로 3칸 또는 오른쪽으로 4칸 순환 이동할 경우 완전히 정렬.

주의사항으로는 배열에는 중복된 요소가 없다. 그리고 target이 배열에 없을 때 -1을 리턴한다.

입출력예시

• let output = rotatedArraySearch([4, 5, 6, 0, 1, 2, 3], 2);
  console.log(output); // --> 5
• output = rotatedArraySearch([4, 5, 6, 0, 1, 2, 3], 100);
  console.log(output); // --> -1

시간복잡도를 개선하는게 advanced문제였다. 그리고 힌트는 이진탐색을 변형하라는 것이었다.

☑ 처음 접근방법

그야말로 단순하게 접근한 것이었다. 배열을 하나하나 조회하면서 만약 target과 일치하면 그 해당인덱스를 내보내고, target을 찾을 수 없다면 -1을 리턴한다는 수도코드를 떠올렸다.

for (let i = 0; i < rotated.length; i++) {
     if (rotated[i] === target) {
       return i;
     }
   }
   return -1;
}

다만 이렇게 접근만 하면 시간복잡도는 개선되지 않는다. 단순하게 처음부터 끝까지 조회하는 것이다. 그래서 입력이 증가하면 처리 시간또는 메모리 사용이 선형적으로 증가하게 된다.

☑ 두번째 접근방법

문제에서 앞서 풀었던 이진탐색을 변형하라는 힌트를 주었다. 배열의 인덱스를 반으로 나누어서 기준이 되는 해당 인덱스의 값과 타겟과 비교한다. 그래서 해당 인덱스의 값보다 타겟이 크다면 큰 쪽의 반뭉텅이만 비교하는 것이다. 만약 이렇게 진행한다면 해당배열은 정렬되어있어야 한다는 전제가 필요하다.

let first = 0// 탐색 대상의 시작 인덱스 값은 0 
let last = arr.length -1 // 탐색 대상의 마지막 인덱스 값
let mid;// mid값 선언 
while (first <= last) {
mid = parseInt((first + last) / 2)
if (target === arr[mid]) {
  return mid;
} 
else {
  if(target < arr[mid]) { last = mid -1 }//요기가 변형되야할듯?
  else { first= mid + 1}//요기도?
  }
}
return -1 
};

앞서 풀었던 문제의 레퍼코드가 이거였어서 이걸 변형하면 될것 같다 생각했지만 맘처럼 잘 안되었다ㅠ(테스트케이스 전원통과가 안됨) 1시간안에 해결을 내야 하는 토이문제였기에 9시 55분까지 삽질과 구글링을 반복하다 이후 레퍼코드를 확인했다.

☑ 레퍼코드

차라리 아예 정렬된 거면 간단한데 완전히 정렬되지는 않았지만 반정도만 정렬된 거라 더 복잡했다. 앞서 나왔던 레퍼코드를 좀 많이(?) 변형하는 형태였다.

• 인덱스를 반으로 뚝 잘라서 왼쪽인덱스 뭉텅이와 오른쪽인덱스 뭉텅이 변수를 할당한다.
• 중간인덱스를 할당해주고, 배열의 중간인덱스 값과 target이 같을 경우엔 해당 인덱스를 리턴한다.
• 배열의 중간인덱스 값과 target이 같지 않을 경우는 왼쪽 뭉텅이를 조회해야할지 아니면 오른쪽 뭉텅이를 조회해야 할지 선택해야한다.(중간인덱스 값이 왼쪽인덱스보다 큰경우와 그 반대의 경우로 나눠야 한다.)
• 중간인덱스 값이 왼쪽인덱스값보다 큰 경우 : 왼쪽뭉텅이를 살핀다.
• 중간인덱스 값이 왼쪽인덱스값보다 작은 경우 : 오른쪽뭉텅이를 살핀다.

수도코드는 이정도로 작성하는게 좋을것 같다. 마지막 부분을 수도코드로 작성하면 너무 길어질 것 같아 코드로 확인하면서 진행하는게 좋을 거 같다. 수도코드를 바탕으로 틀을 한 번 짜보면...

const rotatedArraySearch = function (rotated, target) {
  let left = 0,
  let right = rotated.length - 1;

  while (left <= right) {
    let middle = parseInt((right + left) / 2);

    if (rotated[middle] === target) {
      return middle;
    } // 요기까진 앞서 풀었던 문제와 동일한 형태다. 
    //이제 rotated[middle]과 target이 같지 않을 때를 따져야 한다. 

    if (rotated[left] < rotated[middle]) {
      // 왼쪽 절반이 정렬되어 있는 상태
      
    } else { //rotated[left] > rotated[middle]
      // 오른쪽 절반이 정렬되어 있는 상태
     
    }
  }
  return -1;
};

예시인 4,5,6,0,1,2,3과 target이 2를 생각해보자. 첫번째 경우의 수에 부합하지 않으니 중간 인덱스 값을 기준으로 왼쪽 뭉텅이를 돌지 오른쪽 뭉텅이를 돌지 선택해야 한다. 중간 인덱스 값이 0, target 은 2이다. 왼쪽뭉텅이에선 찾을 수 없으니 오른쪽 뭉텅이를 조회해야 하므로 else문을 가야 한다.

후.. 이제 여기부터가 진짜 인거 같다.

if (rotated[left] < rotated[middle]) {//left의 가장처음시작은 배열의 0번째 인덱스니까 왼쪽뭉텅이를 돈다.
  if(//만약 배열의 중간인덱스 값이 target보다 크면서, target이 배열의 0번째 인덱스보다 크다면
  ) { //배열의 중간값에서부터 1씩 감소시키는 걸 right에 할당한다.
  } else { 
  } // 그렇지 않다면 배열의 중간값에서부터 1씩 증가시키는 걸 left에할당.
} 
else { //right의 가장 처음시작은 배열의 마지막 인덱스니까 오른쪽 뭉텅이를 돈다.
  if(//만약 배열의 맨 마지막인덱스의 값이 target보다 크면서, target이 중간인덱스보다 크다면 
  ) { //배열의 중간값에서부터 1씩 증가시키는 값을 left를 할당한다. 
  } else {
  } //그렇지 않다면 배열의 중간값에서부터 1씩 감소시키는 값을 right에 할당한다. 
}

사실 내가 이해한 바가 맞는지도 확실히 잘 모르겠다ㅠㅠ