[Leetcode] Majority Element

내가 생각한 로직

1. 객체 또는 map을 만들어준다.
2. 인자로 받은 배열 개수를 새며 아이템은 key 값으로, 아이템의 갯수는 value로 저장을 한다.
3. 아이템 중 갯수가 과반수 이상인 것을 return한다.

풀이는 아래와 같다.

let obj = {};
 for(let x of nums){
   obj[x] ? obj[x] = obj[x] + 1 : obj[x] =1
  if(Math.floor(nums.length/2) < obj[x]) {
return x
   }
}

Map을 이용해서 해도 동일한 로직이다.

let map = new Map();
 for(let x of nums){
    map.has(x) ? map.set(x, map.get(x) +1) : map.set(x, 1)
  if(Math.floor(nums.length/2) < map.get(x)) {
return x
   }
}

객체를 이용하지 않고도 풀 수 있는 방법도 있었다(!)

leetcode에서 그리고, 천재 경서님(?)의 도움으로 얻어낸 아이디어(!)

let result = 0;
let count = 0;

for(let i of nums){
	if(count === 0){
    result = i;
    count++;
    } else 
    	{ result === i ? count++ : count--} 
        }
    return result;
    
    }
    	

이건 봐도봐도 어렵긴 한데, 코드도 굉장히 간단하고 기발한 것 같아서 가져왔다.

일단 처음에 result에 배열의 첫번째 값을 가져온다.
그리고 count도 +1 해준다.

계속 result와 같은 값이 나오면 count++을 해주고 다른값이 나오면 count--를 해준다. 그리고 만약 다시 count가 0이 된다면 새로운 result를 넣어줌으로써 계속해서 return할 result를 찾아주는 로직-!

마무리

알고리즘은 내가 문제를 풀었을 때도 재밌지만 다른 사람들의 풀이를 보는 것도 재밌다. 그 중에서도 간단해보이면서도 기발한 코드를 보면 이 세상에 참 천재가 많다는 생각을 한다(?) 위의 방법 언젠간 써먹을거야....⭐️