문제

한 배열 안에서 배열의 1/2 이상 반복되는 수 찾기

분석

이 분석은 Codility의 O(n) 솔루션을 설명한다. (넘나 brilliant...)

• 배열을 돌면서 값을 넣어줄 stack을 준비

• stack의 가장 위 두 값을 비교하여 서로 같으면 남기고, 다르면 기존 원소 하나와 새로 추가된 원소를 삭제한다. (Dominion을 줄이기 위해!)

• 그렇게 해서 마지막 stack에 값이 있으면 그 값은 dominant와는 상관없이 가장 많이 보인 원소임에는 틀림없다.

• 이때 가장 최근에 추가된 원소와 그 전 원소만 비교하므로 꼭 stack이 필요하지는 않다.

코드

const solution = A => {

  let [index, value, count] = [-1,-1, 0];
  
  for(let i=0; i<A.length; i++){
    if(count===0){
      [index, value, count] = [i, A[i], 1];
      continue;
    }

    if(A[i]===value) count++;
    else count--;
  }

  if(count <= 0) return -1;

  let times = A.filter(v => v===value).length;
  if(times > A.length/2) return index;


  return  -1;
}

번외코드

배열을 둘로 나누었을 때, 같은 Dominant 수가 있는 경우의 수를 return하는 문제

• 통 배열에서 dominant한 수가 2개의 sub배열 중 적어도 한 개 이상의 배열에서 dominant하다는 것을 이용

const solution = A => {

  let [leadNum, rCount] = leader(A);
  let lCount = 0;
  if(leadNum === -1) return 0;
  let answer = 0;
  
  for(let i=0; i<A.length; i++){
    if(A[i]===leadNum){
      lCount++;
      rCount--;
    }
    if(lCount > (i+1)/2 && rCount > (A.length - i -1)/2){
      answer++;
    }
  }
  
  return answer;
}

const leader = A => {
  let [value, count] = [-1, 0];
  
  for(let i=0; i<A.length; i++){
    if(count===0){
      [value, count] = [A[i], 1];
      continue;
    }

    if(A[i]===value) count++;
    else count--;
  }

  if(count <= 0) return [-1. -1];

  let times = A.filter(v => v===value).length;
  if(times > A.length/2) return [value, times];

  return [-1. -1];
}