[Algorithm 010] JS - moreThanHalf

Q. 숫자로 이루어진 배열인 nums를 인자로 전달합니다.  숫자중에서 과반수(majority, more than a half)가 넘은 숫자를 반환해주세요.

예를 들어,

nums = [3,2,3]
return 3

nums = [2,2,1,1,1,2,2]
return 2

• 조건 : nums 배열의 길이는 무조건 2개 이상

 

 

A.  처음 답

function mortThanHalf (nums) {
  let obj = {};
  
  nums.forEach((x)=>{
    obj[x] = (obj[x] || 0)+1;
  })
  
  const value = Object.values(obj).sort((a,b) => {return b - a})[0];
  const max = Object.keys(obj).filter((a)=>obj[a]===value?true:false)[0]
  
  return Number(max)
  
}
mortThanHalf([2,2,1,1,1,2,2])

 

✔️해석

function mortThanHalf (nums) {
  let obj = {};
  
  // nums으로 받아오는 배열의 각 요소을 돌며 함수를 실행하겠다.
  // 각 요소를 x라 칭하겠다. 
  nums.forEach((x)=>{   
    obj[x] = (obj[x] || 0) + 1;
    // obj객체의 key로 각 요소 값(x)를 사용하겠다.
    // [2,2,1,1,1,2,2]의 경우?
    // 함수 첫 실행 시, obj[2]가 됨
    // 원래 2라는 key값이 없으니까 새로 추가해 줌 (
    // let obj = { '2' : ?? }가 됨
    // 즉, '2'라는 key값을 세팅하는 용도
    // !! 이때 key값으로 들어가면서 number는 string타입이 됨
    // 그리고 +1 을 함 ('이제 1개가 있다!')
    // let obj = { '2' : 1 }
    
    // 두번 째 실행시, 
    // 되고 obj[2]되고, 이번엔 { '2' : 1 } 가 있으므로 
    // obj[2] = (obj[2]의 값) + 1
    // let obj = { '2' : 2 }
    // 이렇게 쭉 돌아감
    
  })    // { '1': 3, '2': 4 }
  
  const value = Object.values(obj).sort((a,b) => {return b - a})[0];
  // Object.values()로 obj객체의 value만으로 이루어진 배열을 구함
  // [ 3, 4 ]
  // 이 배열의 값들(values)을 sort()메서드를 사용해 내림 차순으로 정렬함
  // [ 4, 3 ]
  // 그 중 1번 째 값을 value라는 변수에 담음
  // [ 4 ]

  const max = Object.keys(obj).filter((a)=>obj[a]==value?true:false)[0]
  
  // Object.keys()로 obj객체의 key만으로 이루어진 배열을 구함(key값이라 string으로 담김)
  // [ '1', '2' ]
  // 이 배열의 값(keys)을 이용해 배열을 순회하면서 filter()메서드를 사용해 value값인 4와 같은 같을 가진 요소(key)를 찾아 배열로 만듦
  // [ '2' ]
  // 그 중 1번 째 값을 max에 담음
  
  return Number(max) 
  //string인 max 값을 number형으로 변환해서 반환
  
}
mortThanHalf([2,2,1,1,1,2,2])

• forEach()  :  주어진 함수를 배열 요소 각각에 대해 실행   MDN명세
• sort()   MDN명세

// 오름차순 정렬
arr.sort((a,b) => {return a - b});

// 내림차순 정렬
arr.sort((a,b) => {return b - a});

• filter() : 주어진 함수의 테스트를 통과하는 모든 요소를 모아 새로운 배열로 반환   MDN명세
• Number() : 문자열을 숫자로 변환     MDN명세

 

 

하지만 const max값을 선언하는 부분에서

• const value의 값은 1개의 number형 값
• key에는 중복된 값이 없음
• 동등연산자의 기본값은 boolean형이므로 true:false 를 따로 설정할 필요 없음
• Number()메서드는 배열값도 숫자로 바꿔 줌

위와 같은 이유로 이렇게 줄일 수 있다.

function moreThanHalf(nums) {
  let obj = {};
 
  nums.forEach((x) => {
    obj[x] = (obj[x] || 0) + 1;
  })

  const value = Object.values(obj).sort((a,b) => {return b - a})[0])
  const max = Object.keys(obj).filter((e)=>obj[e]==value)
  
  return Number(max)
}

 

 

포스팅 중에 인지한 문제!

위 로직에서는 다음과 같이 3이 과반수를 넘지 않은 경우에도 3을 출력해주고 있었다.

 

문제를 다시 보면

숫자중에서 과반수(majority, more than a half)가 넘은 숫자를 반환

이라고 되어있고, 내가 처음으로 구한 로직은 가장 많이 있는 숫자를 반환한 것

// 위 로직의 결과 : 3이 과반수를 넘지 않는데 3을 반환하고 있다.
nums = [2,2,1,1,1,3,3,3,3]
return 3

// nums.length를 2로 나눠 전제 배열의 과반수를 초과하는 수를 구한다.
// 배열의 길이가 홀수일 경우도 있으므로, Math.floor()를 사용해 내림을 한다.
// 배열의 길이가 7일 경우 7 / 3 = 3.5. 이 값을 내림하면 3
// 즉, 배열에서 제일 많은 숫자가 4개 보다 많아야 과반수가 되는 것

if(Math.floor(nums.length / 2) < value){
	return Number(max)  
}else{
	return '가장 많은 수 :'+ max
}

 

 

B.  최종 답

 

function moreThanHalf(nums) {  
  let obj = {};
  
  nums.forEach((x) => {
    obj[x] = (obj[x] || 0) + 1;
  })
  
  const value = Object.values(obj).sort((a,b) => {return b - a})[0];
  const max = Object.keys(obj).filter((e)=>obj[e]==value)
 
  if(Math.floor(nums.length / 2) < value){
    return Number(max)  
  }else{
    return '가장 많은 수 :'+ max
  }
  
}

moreThanHalf([2,2,1,1,1,3,3,3,3,3,3])    // 3
moreThanHalf([2,2,1,1,1,3,3,3,3,3])      // '가장 많은 수 :3'