2021.8.7 TIL 공통 원소, 연속 부분수열 합, k일 연속 최대 매출합

공통 원소

A, B 두 개의 집합이 주어지면 두 집합의 공통 원소를 추출하여 오름차순으로 출력

 

function solution(a, b) {
  let answer;
  // code here;
  return answer;
}
let a = [1, 3, 9, 5, 2];
let b = [3, 2, 5, 7, 8];
console.log(solution(a, b)); // [2,3,5]

 

 

답) 중복을 허용하지 않는 Set()을 이용

 

function solution(a, b) {
  let answer = [];
  let mySet = new Set(a);

  for(let el of b) {
    mySet.has(el) ? answer.push(el) : null;
  }

  return answer.sort((a, b) => a - b);
}

 

 

답2) 두 배열을 오름차순으로 정렬한 뒤, 각 원소를 돌면서 중복된 원소를 담아주기

 

function solution(a, b) {
  let answer = [];
  let flagA = flagB = 0;
  a.sort((c, d) => c - d); // sort()는 mutable
  b.sort((c, d) => c - d);

  while(flagA < a.length && flagB < b.length) {
    if(a[flagA] === b[flagB]) {
      answer.push(a[flagA++]);
      flagB++;
    } else {
      a[flagA] < b[flagB] flagA++ : flagB++;
    }
  }

  return answer;
}

 

 

연속 부분수열 1

수열이 주어질 때, 연속한 원소의 합이 타겟한 숫자와 같은 경우의 수는?

 

function solution(num, arr) {
  let answer;
  // code here;
  return answer;
}
let a = [1, 2, 1, 3, 1, 1, 1, 2];
console.log(solution(6, a)); // 3

 

 

답) two pointer algorithm

 

function solution(num, arr) {
  let answer = 0;

  for(let i = 0; i < arr.length; i++) {
    let sum = arr[i];
    let idx = i + 1;

    if(sum === num) {
      answer++;
    };

    while (num > sum) {
      sum += arr[idx++];
      if(sum === num) {
        answer ++;
      };
    }
  };

  return answer;
}

 

 

연속 부분수열 2

수열이 주어질 때, 연속한 원소의 합이 타겟보다 작은 경우의 수는?

 

function solution(num, arr) {
  let answer;
  // code here;
  return answer;
}
let a = [1, 3, 1, 2, 3];
console.log(solution(5, a)); // 10

 

 

답) two pointer algorithm

 

function solution(num, arr) {
  let answer = 0;

  for(let i = 0; i < arr.length; i++) {
    let sum = 0;
    let idx = i;

    while(sum <= num) {
      sum = arr[idx++];
      if(sum === num) answer++;
    };
  };

  return answer;
}

 

 

k일 연속의 최대 합

매출의 배열이 주어질 때, k 일 연속의 합 중에서 최대값은?

 

function solution(num, arr) {
  let answer;
  // code here;
  return answer;
}
let a = [12, 15, 11, 20, 25, 10, 20, 19, 13, 15];
console.log(solution(3, a)); //56

 

 

답) two pointer algorithm

 

function solution (num, arr) {
  let answer = 0;

  for(let i = 0; i < arr.length - 2; i++) {
    let sum = arr[i];
    let cnt = i + 1;

    while(cnt - i < num) {
      sum += arr[cnt++];
    }
    answer = Math.max(sum, answer);
  };

  return answer;
}

 

 

답2) sliding door algorithm

3일 째 연속의 최대 합을 구할 때, 매출의 배열 [12, 15, 11, 20, 25, ... 생략]이다.

• sum = 12 + 15 + 11
• sum = (sum + 20) - 12
• sum = (sum + 25) - 20
• 반복

 

function solution(num, arr) {
  let answer = sum = 0;

  for(let i = 0; i < num; i++) {
    sum += arr[i]
  };

  answer = sum;

  for(let i = k; i < arr.length; i++) {
    sum += (arr[k] - arr[i - k]);
    answer = Math.max(sum, answer);
  }

  return answer;
}