29 이진탐색 변형

const rotatedArraySearch = function (rotated, target) {
  let low = 0;
  let high = rotated.length -1;
  while (low <= high){
    let mid = parseInt((high + low) / 2);
    if(target === rotated[mid]){
      return mid;
    } else if (rotated.length % 2 === 0 ){
      if (rotated[mid] > target){
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    } else {
      if (rotated[mid] > target){
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }    
  }
  return -1;
};

• [6, 8, 9, 10, 15, 4], 15 이렇게 찾아보면 패스가 안됨
  이전에 문제를 풀때,
  배열에 짝수개의 요소가 들어갔을때와 홀수개의 요소가 들어갔을때로 나누어서 생각을 했었다.
  [3,4,0,1,2] 이런식... 또는
  [5,6,7,1,2,3] 이런식으로 예시를 생각했고 그래서
  0(가장 작은수가)이 middle이 될때와 7(가장 큰수)이 middle이 될때를 나누어서 코드를 짜야겠다 해서 저렇게 짰었음. 가장 큰수와 가장 작은수 사이가 분기가 된달까. 근데 효율적인 알고리즘이 아니라고ㅠㅠ...

다시 문제를 풀어보다가

const rotatedArraySearch = function (rotated, target) {
  let start = 0;
  let last = rotated.length - 1;
  
  while(start <= last){
    let middle = parseInt((start + last) /2);
    if(rotated[middle] === target) return middle;

    if(rotated[middle] > target){
      start = middle +1
    } else if(rotated[middle] < target) {
      last = middle -1
    }
  }
  return -1;
};

이렇게만 해서 분기를 나누어줬는데 반절만 테스트가 패스되더라.
테스트케이스와 레퍼런스 코드를 보면서 분기를 더 세분화해야한다는 것을 깨달았다.
마치 이전에 내가 length가 홀수인지 짝수인지로 분기를 나누어줬던 것처럼.
테스트케이스 기반으로 조건을 하나씩 더 넣다보니 레퍼런스코드와 같은 코드가 나왔다.

if (rotated[start] < rotated[middle]) {
      if (target < rotated[middle]) {
        last = middle - 1;
      } else {
        start = middle + 1;
      }
    } else {
      if (rotated[middle] < target) {
        start = middle + 1;
      } else {
        last = middle - 1;
      }
    }

나는 뭔가 숫자만 나오면 머리가 더 안돌아가는 경향이 있는데ㅎ 그래도 한번 더 풀어보니까 왜 이렇게 되는지 이해가 되어서 다행이었다.

middle이 0번째 인덱스에 있는 수보다 큰경우와 아닌 경우로 첫번째 분기를 해주고,
그 안에서 타겟이 middle보다 큰지 작은지로 분기를 해준다.
그리고 타겟이 middle보다 작은데 start보다 작은 경우도 있을 수 있고, 타겟이 middle보다 큰데도 last보다 큰 경우도 있을 수 있으니 &&연산자로 조건을 더 견고하게 해준다.
이렇게 말로 써놓으니까 이상한데 예를 들어서
[9, 10, 15, 4, 6, 8]에서 6을 찾는 경우
middle(15)이 start(9)보다 크고
타겟(6)이 middle(15)보다 작은데
이때 last = middle -1해주면 last는 4가 되고, 그럼 middle은 2가 된다.
2면 middle은 다시 15가 되고, last는 3이 되고 middle은 1이 되고 영영 6이 있는 자리에서는 멀어지게 된다... 이때
rotated[start] <= target 라는 조건을 더 붙여주면
타겟(6)보다 start(9)가 작기 때문에 else문으로 빠져 left가 3이 되고 middle은 4가 되니 6을 바로 찾을 수 있게 된다.

반대의 경우에도 마찬가지로
target <= rotated[last] 조건을 준다.
[10, 11, 12, 3, 6, 7, 8, 9], 11 이 테스트케이스를 통과할 수 있다.

    if (rotated[start] < rotated[middle]) {
      if (rotated[start] <= target) {
        last = middle - 1;
      } else {
        start = middle + 1;
      }
    } else {
      if (target <= rotated[last]) {
        start = middle + 1;
      } else {
        last = middle - 1;
      }
    }

테스트를 하면서 이렇게 작성시 효율적인 알고리즘이 아니라는 것을 알게 되었다. 여기서는 middle과의 비교가 조건문에서 빠졌을 뿐이다.
내 코드에는 middle만 비교하는데 low, high도 비교하는 조건문을 추가하면 통과가 되지 않을까 싶다!

30 브라켓 짝 맞추기

const balancedBrackets = function (str) {
  if(!str) return true;
  let bool = false;
  let temp = [];

  let arr = str.split('');
  // if(el === '(' && arr.includes(')')) return true;
  //'(' 가 먼저오고 ')'가 그 뒤에 와야함.
  //짝이 맞아야함.
  if(str.length % 2 !== 0) return false;

  for(let i = 0; i < arr.length; i++){
    if(arr[i] === '(' && arr[i+1] === ')') temp.push(arr[i], arr[i+1]);
    if(temp.join('') === '()') bool = true;
    else bool = false;
  }
  
  return bool;
};