[코테챌린지] 1287. Element Appearing More Than 25% In Sorted Array

1287. Element Appearing More Than 25% In Sorted Array

이 문제는 정렬된 배열 중 25%의 이상을 차지하는 요소가 있다면 해당 요소를 반환하라.
문제 자체의 이해는 잘 됨.

우선 이 문제를 직면했을때, 요즘 map object 에 빠져가지구 그냥 뭐 생각도 안하고 map으로 풀려고 접근을 함.

var findSpecialInteger = function(arr) {
  let length = arr.length;
  let compare = Math.floor( length / 4);
  let map = {};
  
    //예외처리
    
    if(arr.length === 0) return false;
    
  
  for(let i=0; i<arr.length; i++) {
    
    if(!map[arr]) map[arr] == 1;
    console.log(map);
    
    
    if(map[arr[i]]) { return arr[i] };
    
  }
    
    return false;
};

=> 내가 해결하려고 했던 방법은 arr[i] 의 숫자를 카운트해서 map 객체에 넣고 그 숫자를 25%의 숫자랑 비교를 하려고 했다. 뭐 풀면 나올꺼 같긴한데, 값들을 저장하는 Space 면에서 굉장히 비효율적이라는 걸 알게 됨. 이게 테스트라면 왠지 떨어졌을듯 ..

그래서 좀 힌트를 얻어보고자 다른 분들이 푼걸 봤고 한대 맞은거 같은 해결법
이렇게 쉬운 문제를.. 꼬아서 생각했더니..

var findSpecialInteger = function(arr) {

    let compare = Math.floor(arr.length / 4);
    
    if(arr.length === 0) return -1;
    if(arr.length === 1) return arr[0];
    
    for(let i=0; i<arr.length; i++) {
        if(arr[i] === arr[i+compare]) return arr[i];
    }
    
    return -1;
};

이건 정렬된 배열 이라는 걸 잊지말자! 값이 윈도우의 첫번째 요소와 25%를 나타내는 숫자를 더한 요소값이 같으면 전체가 다 같다. 그러니 그 숫자는 25% 이상 있는 것이다.