[Q01] RotatedArraySearch

1. 문제

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

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

1 - 1) 입력

인자 1 : rotated

• number 타입을 요소로 갖는 배열
• rotated[i]는 정수

인자 2 : target

• number 타입의 정수

1 - 2) 출력

number 타입을 리턴해야 합니다.

1 - 3) 주의사항

rotated에 중복된 요소는 없습니다.

target이 없는 경우, -1을 리턴해야 합니다.

1 - 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

1 - 5) Advanced

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

1- 6) 힌트

이진 탐색(binary search)을 약간 변형하여 해결합니다.

---

2. 나의 풀이

2 - 1) 코드

const rotatedArraySearch = function (rotated, target) {

    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;
  };

 

2 - 2) 코드 + 풀이 과정 해설

const rotatedArraySearch = function (rotated, target) {
    // TODO : 여기에 코드를 작성합니다.
    // 이진 탐색 : 임의의 중앙값을 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식
    // 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다. 
    // 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 
    // 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다.
    // 출처 : https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%EA%B2%80%EC%83%89_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
  
    // index로 사용할 변수 설정
    let start = 0;
    let end = rotated.length-1;
    let mid;
  
    while(start <= end){
      // 중앙값 계산
      // 정수값을 얻기 위해 Math.floor() 함수 사용
      mid = Math.floor((start + end) / 2);
  
      // 배열 내에서 target 값을 찾은 경우 해당 index를 리턴하며 함수 종료
      if(rotated[mid] === target) return mid;
  
      // 주어진 '부분 오름차순 정렬' 배열을 반으로 잘랐을 때, 
      // 잘린 부분의 어느 한 쪽은 반드시 오름차순 정렬되어있으므로
      // 정렬된 곳을 기준으로 이진 탐색을 수행하고,
      // 그 결과에 따라 start, end 포인트를 변경해준다.
      // 정렬된 곳에 target 값이 있느냐 없느냐에 따라 start, end 포인트 설정이 달라짐
  
      // mid 기준 왼쪽이 정렬되어 있고
      if(rotated[start] <= rotated[mid]){
        // 해당 범위 내에 target 값이 존재한다면 mid-1을 새로운 최댓값으로 설정한다.
        if(rotated[start] <= target && target < rotated[mid]){
          end = mid-1;
        }else{
          // 해당 범위 내에 target 값이 존재하지 않는다면 = mid 기준 오른쪽에 target 값이 존재
          // mid+1을 새로운 최솟값으로 설정한다.
          start = mid+1;
        }
      }else{
        // mid 기준 오른쪽이 정렬되어 있고
        // 해당 범위 내에 target 값이 존재한다면 mid+1을 새로운 최솟값으로 설정한다.
        if(rotated[mid] < target && target <= rotated[end]){
          start = mid+1;
        }else{
          // 해당 범위 내에 target 값이 존재하지 않는다면 = mid 기준 왼쪽에 target 값이 존재한다는 의미이므로
          // mid-1을 새로운 최댓값으로 설정한다.
          end = mid-1;
        }
      }
    }
  
    // 반복문 실행 종료 && 함수 종료x = target과 일치하는 값이 rotated에 존재하지 않음
    return -1;
  };

---

3. 레퍼런스 코드 분석

// naive solution
// const rotatedArraySearch = (rotated, target) => {
//   for (let i = 0; i < rotated.length; i++) {
//     if (rotated[i] === target) {
//       return i;
//     }
//   }
//   return -1;
// };

const rotatedArraySearch = function (rotated, target) {
    let left = 0,
    right = rotated.length - 1;
  
    while (left <= right) {
      let middle = parseInt((right + left) / 2);
  
      if (rotated[middle] === target) {
        return middle;
      }
  
      if (rotated[left] < rotated[middle]) {
        // 왼쪽 절반이 정렬되어 있는 상태
        if (target < rotated[middle] && rotated[left] <= target) {
          right = middle - 1;
        } else {
          left = middle + 1;
        }
      } else {
        // 오른쪽 절반이 정렬되어 있는 상태
        if (target <= rotated[right] && rotated[middle] < target) {
          left = middle + 1;
        } else {
          right = middle - 1;
        }
      }
    }
  
    return -1;
  };

---

4. 학습 중 궁금해서 찾아본 부분

1. parseInt()
   • 문자열 인자를 파싱하여 특정 진수(수의 진법 체계에서 기준이 되는 값)의 정수를 반환하는 함수
   • parseInt 함수는 첫 번째 인자를 문자열로 변환하고, 그 값을 파싱하여 정수나 NaN을 반환합니다.
   • 출처 : https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/parseInt
2. Math.floor()
   • 주어진 숫자와 같거나 작은 정수 중에서 가장 큰 수를 반환하는 함수
   • 출처 : https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Math/floor
   • 사용예

      // Math.floor( 45.95); //  45
      // Math.floor( 45.05); //  45
      // Math.floor(  4   ); //   4
      // Math.floor(-45.05); // -46
      // Math.floor(-45.95); // -46

 

※ 추가로 학습하면 좋은 내용 : Number(), parseInt(), parseFloat()의 차이점과 공통점

https://velog.io/@loocia1910/Number-parseInt-parseFloat-%EC%B0%A8%EC%9D%B4%EC%A0%90%EA%B3%BC-%EA%B3%B5%ED%86%B5%EC%A0%90JavaScript

Number(), parseInt(), parseFloat() 차이점과 공통점[JavaScript]

---

5. 학습 후기

시간 복잡도를 개선해야 통과되는 문제들이 너무 어렵다ㅠ

이런 문제를 만나면 '문제 풀이 도전 -> 모르겠음 -> 검색 -> 참고하여 코드 작성'이라는 과정을 거쳐 제출만 겨우 하고 있다. 

이대로 괜찮은가 나의 코딩테스트...걱정되는구먼...나의 미래가...ㅋㅋㅋㅋㅋ

그래도 풀다 보면 나아지겠지? 나중엔 이런 문제따위 발가락으로도 풀길 바라며 후기는 여기에서 마침!