문제 : rotatedArraySearch

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

• 부분적으로 정렬된 배열: 배열을 왼쪽 혹은 오른쪽으로 0칸 이상 순환 이동할 경우 완전히 정렬되는 배열
• 예시: [4, 5, 6, 0, 1, 2, 3]은 왼쪽으로 3칸 또는 오른쪽으로 4칸 순환 이동할 경우 완전히 정렬됩니다.

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

문제의 접근

부분적으로 정렬된 배열 다시말해 쉽게 모두 정렬된 배열로 만들어 줄 수 있다.

let cnt = 0;
  while(true){
    if(rotated[0] > rotated[1]){
      let num = rotated.shift()
      rotated.push(num)
      cnt++;
      break;
    }
    let num = rotated.shift();
    rotated.push(num)
    cnt++;
  }

다음 코드를 통해서 부분 정렬된 배열을 온전히 정렬된 배열로 만들어 줄 수 있다. 그리고 그 이동한 만큼의 인덱스도 cnt에 기억시켜둘 수 있다. 이제 여기서 이전에 배운 binary search를 실행하면 된다.

const rotatedArraySearch = function (rotated, target) {
  // TODO : 여기에 코드를 작성합니다.
  let cnt = 0;
  while(true){
    if(rotated[0] > rotated[1]){
      let num = rotated.shift()
      rotated.push(num)
      cnt++;
      break;
    }
    let num = rotated.shift();
    rotated.push(num)
    cnt++;
  }

  let start = 0;
  let end = rotated.length - 1;
  let mid;
  while(start <= end){
    mid = Math.floor((start + end) / 2)
    if(rotated[mid] === target){
      return (mid + cnt) % rotated.length;
    }else if(rotated[mid] > target){
      end = mid - 1;
    }else{
      start = mid + 1;
    }
  }
  return -1;
};

위 코드를 실행하면 원하는 인덱스는 추출이 가능하지만 테스트는 통과하지 못한다. 아마 이것도 Advanced 레벨을 한번에 통과해야하는 모양이다.

Advanced

아마 위의 코드는 시간 복잡도가 효율성이 많이 떨어지는 것 같다. 그도 그럴 것이 첫번째 while문이 그냥 for문을 쓰는 것만 못한 것 같다. 그렇다면 이걸 어떻게 해야할까 한번 더 고민해봤다.

const rotatedArraySearch = function (rotated, target) {
  // TODO : 여기에 코드를 작성합니다.
  let start = 0;
  let end = rotated.length - 1;
  let mid;
  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;
      }else{
        start = mid+1;
      }
    }else{ //오른쪽 절반이 정렬되어 있으면
      if(rotated[mid] <= target && target <= rotated[end]){
        start = mid+1;
      }else{
        end = mid-1;
      }
    }

  }
  return -1;
};

문제에 힌트가 있었다. binary search를 조금만 변경해주면 됬다. 조금 더 세부적으러 나눠서 값을 찾아 들어가면 된다.

문제를 통해 생각해 볼 것

확실히 문제가 조금 복잡해지니깐 다른 삽질을 너무 많이 했다. 저 결론을 도달하기 까지 정말 많은 생각을해야했다. 솔직히 말하면 시간초과를 했다. 그럼에도 붙들고 생각해낸 결과이기에 만족은 하되 100% 만족스럽지는 못하다. 다른 공부할 시간을 잡아먹으면서 생각해낸 것이 아깝다...