알고리즘 문제풀이 8

이진탐색트리와 관련된 알고리즘 문제다.
주어진 배열 내에서 원하는 요소의 유무를 파악하고 있으면 그 요소의 인덱스값을 리턴해주는 문제를 해결해야하는 알고리즘 문제였다.
보통 요소의 인덱스 값을 찾으면 indexOf 메소드를 활용해준다. 이는 주어진 배열의 수를 한 번 순회해주는 것으로 시간 복잡도가 O(N)이다. 하지만 문제에서 요구한 점은 시간복잡도 O(logN)이었다.

이진탐색트리란 무엇일까?

자료구조를 공부하다보면 배우게될 트리구조가 있다. 일종의 나무를 뒤집어 놓은 모양대로 자료구조가 짜여져 있는 것이다. 보통의 트리 구조는 하나의 뿌리(root)가 있으면 거기서 가지가 얼마든지 만들어진다.(자식 노드) 그러나 이진트리는 한 뿌리(혹은 부모노드당) 자식 노드를 단 두개만 가질 수 있다.

그리고 여기서 이진탐색트리는 추가적인 규칙을 지니고 있다.
1. 왼쪽의 자식 노드는 부모노드보다 무조건 작다.
2. 오른쪽의 자식 노드는 부모노드보다 무조건 크다.

어떻게 보면 정해진 요소를 탐색하고자 할 때, 이진탐색트리를 활용하게 된다면, 찾으려는 수가
해당 자료구조의 root수보다 작냐 크냐에 따라서 배열의 일부만 탐색하게 된다.

따라서 이진탐색트리를 활용한다면 원하는 요소를 찾고 탐색하는 문제를 시간복잡도 O(logN)으로 해결가능하다.

• 처음에는 임의의 중간수를 정의하여 풀어주었는데, 생각해보니 그렇게 하면 재귀함수가 진행될수록 인덱스값이 자꾸 바뀌었다. 따라서 인덱스 값들을 고정시켜준채로 재귀해야했다.
• 주어진 배열에서 이진탐색트리의 논리로 요소를 찾는 분기?(if문 조건 나누기)를 어떻게 해야할 지 이해가 가지 않았다. 왜냐면 주어진 배열은 크기순으로 정렬된 배열이 아닐 확률이 높기 때문이다. 그렇다고 정렬을 해주고 계산해주자니, 기존의 인덱스 구성이 다 깨져 버린다.
  => 이건 문제를 다시 읽어보니 "정렬되어 있는 배열 중 일부를 왼쪽 혹은 오른쪽으로 회전시킨 배열이 주어졌을때" 라고 되어있다. 즉 특정 요소를 중심으로 양쪽은 제대로 정렬되어있다.

/*
 * 정렬되어 있는 배열 중 일부를 왼쪽 혹은 오른쪽으로 회전시킨 배열이 주어졌을때,
 * 어떻게 특정 element를 효율적으로 찾을 수 있을까요?
 *
 * 작성한 함수는 target의 index값을 return하고, 없으면 null을 return해야 합니다.
 *
 * 예시 :
 * rotatedArraySearch([7 ,8, 9,10, 0, "1", 2, 3, 4, 5, 6 ], 2) === 5
 *
 * rotatedArraySearch([4, 5, 6, 0, 1, 2, 3], 100) === null
 *
 * 시간 복잡도가 O(log(array.length))이 되도록 도전해 보세요!
 */
const rotatedArraySearch = function (rotated, target) {
  //우선 주어진 배열의 첫번째와 마지막 인덱스를 정의
  let firstidx = 0;
  let lastidx = rotated.length - 1;
  
  function find(first, last) {
    //첫번째 인덱스 값으로 오는 first가 last보다 크면 안된다.
    if (first > last) {
      return null;
    }
    //임의로 중간 인덱스를 정의
    let mididx = Math.floor((first + last) / 2);
    // 1. 임의의 인덱스 값과 타겟값이 같으면 해당 인덱스값 리턴
    if (target === rotated[mididx]) {
      return mididx;
    }
   //요소가 하나인 경우에도 재귀를 돌수있다. 숫자와 undefined 의 비교는 false를 주긴 한다!(이건 자바스크립트에서만)
    //그런데 다른 언어에서는 위와 같은 부분에서 에러가 발생할 수 있다.
    //따라서 첫 인덱스와 마지막 인덱스가 같으면 이라는 조건을 걸어두는 것이 좋다.
    if(first === last){
      if(rotated[first] === target){
        return first
      } else {
        return null
      }
    }
    //결론적으로 아래의 조건이 없어도, 문제 없다.
    // 2. 비교하는 가상의 배열의 길이가 3개이하일때를 말한다.
    //if (mididx <= 1) {
     // if (target === rotated[first]) {
    //    return first;
    //  } else {
        //이미 위의 조건문에서 mididx에 해당하는 값은 일치하지 않는다고 나왔으므로, 재귀를 돌릴때 mididx는 고려X
    //    return find(mididx + 1, last);
    //  }
   // }
    //해당 중간값을 기준으로 양쪽이 제대로 정렬되어있는지 점검
    //우선 기준점의 앞쪽부터 점검
    if (rotated[first] < rotated[mididx - 1]) {
      //앞쪽이 제대로 정렬되어있다면, 찾고자 하는 수가 앞쪽에 있는지 확인
      if (target >= rotated[first] && target <= rotated[mididx - 1]) {
        //앞쪽에 있는 경우에만 재귀돌려주기
        return find(first, mididx - 1);
      } else {
        return find(mididx + 1, last);
      }
    } else {
      //앞쪽이 제대로 정렬되어있지 않은 경우 ex) [7,8,9,10,0]
      //아래의 코드는 내가 생각한 예시의 코드에만 해당되어 버린다.
      //따라서 적절한 조건은, 위에서 앞에 정렬되어있는지를 본다음, 아니면
      //뒤에 내가 찾고자 하는것이 있는지 점검하고, 없으면 다시 앞쪽으로 돌아간다로 하는것이 맞다
      if(target >= rotated[mididx+1] && target <= rotated[last]){
        //맨끝요소를 제외한 가상의 배열에 타겟이 있는 경우만 재귀를 넣어주고
        return find(mididx+1, last);
      } else {
        return find(first, mididx-1);
      }
      //if (target === rotated[mididx - 1]) {
        //앞쪽의 가장 끝요소 즉 중간인덱스에서 -1한 인덱스의 요소가 타겟과 같은지 검사
      //  return mididx - 1;
     // } else if (target >= rotated[first] && target <= rotated[mididx - 2]) {
        //맨끝요소를 제외한 가상의 배열에 타겟이 있는 경우만 재귀를 넣어주고
      //  return find(first, mididx - 2);
     // } else {
     //   return find(mididx + 1, last);
     // }
   // }
  }
  return find(firstidx, lastidx);
};

위의 문제를 해결하니, 정렬된 배열에 대한 이진탐색트리는 좀 더 쉽게 풀렸다.

/*
 * 정렬된 배열이 주어졌을때, 이진 탐색 알고리즘을 이용하여 특정 요소의 인덱스값을 return하는 함수를 작성하세요.
 *
 * 예시 :
 *
 * let index = binarySearch([1, 2, 3, 4, 5], 4);
 * console.log(index); // [3]
 *
 * 참고 : https://qph.fs.quoracdn.net/main-qimg-742d049387316193be2d097fe7a499de
 */

const binarySearch = function (array, target) {
  //임의의 난수 만들어서 그 난수 인덱스에 위치한 랜덤한 기준값뽑아내기
  //여기서 임의의 수를 나는 중간값으로 할 것이다
  //첫번째 코드 짤때는 배열 내의 값으로 비교를 하니까 나중에 결국 값의 인덱스를 찾기위해 indexOf 메소드를 사용해야했다.
  //따라서 index값을 나중에 구할수있도록 index값들끼리 비교해야한다.
  function findIndex(first, last) {
    if (first > last) {
      return null;
    }
    //요소가 하나인 경우에도 재귀를 돌수있다. 숫자와 undefined 의 비교는 false를 주긴 한다!(이건 자바스크립트에서만)
    //그런데 다른 언어에서는 위와 같은 부분에서 에러가 발생할 수 있다.
    //따라서 첫 인덱스와 마지막 인덱스가 같으면 이라는 조건을 걸어두는 것이 좋다.
    if(first === last){
      if(rotated[first] === target){
        return first
      } else {
        return null
      }
    }
    let midKey = Math.floor((first + last) / 2);
    if (target === array[midKey]) {
      return midKey;
    }
    //if (last - first <= 2) {
     // if (target === array[first]) {
     //   return first;
     // } else {
     //   return findIndex(midKey + 1, last);
     // }
   // }
    if (array[midKey] > target) {
      return findIndex(0, midKey - 1);
    } else if (array[midKey] < target) {
      return findIndex(midKey + 1, array.length - 1);
    }
  }
  return findIndex(0, array.length - 1);
};