[코딩 테스트 문제 + 풀이] Flags, Greatest Common Divisor Algorithm, Caterpillar method, Greedy Algorithms

 

 

Q. Flags

 

function solution(A) {
  let peaks = new Array(A.length);
  let nextPeak = A.length;
  peaks[A.length - 1] = nextPeak;
  for (let i = A.length -2; i > 0; i--) {
    if(A[i - 1]< A[i] && A[i + 1] < A[i])
    nextPeak = i;
    peaks[i] = nextPeak;
  }
  peaks[0] = nextPeak;

  let current_guess = 0;
  let next_guess = 0;
  while (canPlaceFlags(peaks, next_guess)) {
    current_guess = next_guess;
    next_guess += 1;
  }
  return current_guess;
}

function canPlaceFlags(peaks, flagsToPlace) {
  let currentPosition = 1 - flagsToPlace;
  for (let i = 0; i < flagesToPlace; i++) {
    if (currentPosition + flagsToPlace > peaks.length - 1)
    return false;
    currentPosition = peaks[currentPosition + flagsToPlace];
  }
  return currentPosition < peaks.length;
}

console.log(solution([1, 5, 3, 4, 3, 4, 1, 2, 3, 4, 6, 2]));

 

 

 

 

 

Greatest Common Divisor Algorithm

 

Q. Chocolates By Numbers Problem

 

function findGcd(a, b) {
  if(b === 0)
    return a;
  else
    return findGcd(b, a % b);
}

function solution(N, M) {
  return N / findGcd(N, M);
}

console.log(solution(10, 4));  // 5

 

 

 

 

 

Caterpillar method

 

Q. Count Distinct Slices

 

function solution(M, A) {
  let totalSlices = 0;
  let inCurrentSlice = new Array(M + 1).fill(false);
  let head = 0;
  for (let tail = 0; tail < A.length; tail++) {
    while (head < A.length && !inCurrentSlice[A[head]]) {
      inCurrentSlice[A[head]] = true;
      totalSlices += (head - tail) + 1;
      head += 1;
      if (totalSlices > 1000000000)
      totalSlices = 1000000000
    }
    inCurrentSlice[A[tail]] = false;
  }
  return totalSlices;
}

console.log(solution(6, [3, 4, 5, 5, 2]));

 

 

 

 

 

 

Q. Min Abs Sum Of Two

 

function solution(A) {
  let minAbsSumOfTwo = Number.MAX_SAFE_INTEGER;
  A.sort(function (a,b) {return a -b});
  let head = 0;
  let tail = A.length - 1;
  while (head <= tail) {
    minAbsSumOfTwo = Math.min(minAbsSumOfTwo, Math.abs(A[head] + A[tail]));
    if (A[head] + A[tail] < 0) head++;
    else tail--;
  }
  return minAbsSumOfTwo;
}

console.log(solution([8, 3, 5, 16, 11]));   // 6

 

 

 

 

 

 

Greedy Algorithms

: local best choice -> optimal global solution

 

 

Q. Max Non Overlapping Sgments

 

function solution(A, B) {
  let lastEndSegment = -1;
  let chosenCount = 0;

  for (let i = 0; i < A.length; i++) {
    if (A[i] > lastEndSegment) {
      chosenCount++;
      lastEndSegment = B[i];
    }
  }
  return chosenCount;
}

console.log(solution([1, 3, 7, 9, 9], [5, 6, 8, 9, 10]));   // 3

 

 

 

 

 

 

Q. Tie Ropes

 

function solution(K, A) {
  let count = 0;
  let ropeLength = 0;
  A.forEach(rope => {
    ropeLength += rope;
    if (ropeLength >= K) {
      count++;
      ropeLength = 0;
    }
  }); 

  return count;
}

console.log(solution(4, [1, 2, 3, 4, 1, 1, 3]));    // 3