[코딩 테스트 문제 + 풀이] Maximum Array, Sorting Algorithms, Prefix Sums

 

 

Q. Maximum Sub Array problem (Maximum seperate problem)

 

function solution(A) {
  let globalMaxSum = 0;
  let localMaxSum =0;
  for (let i = 1; i < A.length; i++) {
    let d = A[i] - A[i - 1];
    localMaxSum = Math.max(d, localMaxSum + d);
    globalMaxSum = Math.max(localMaxSum, globalMaxSum);
  }
  return globalMaxSum;
}

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

 

 

 

 

 

 

 

 

 

 

 

 

 

Q. Disc Intersection Code

 

function solution(A) {
  let len = A.length;
  let discHistory = new Array(len * 2);
  let j = 0;
  for (let i = 0; i < len; i++) {
    discHistory[j++] = new DiscLog(i - A[i], 1);
    discHistory[j++] = new DiscLog(i + A[i], -1);
  }
  discHistory.sort(compare)
  let intersections = 0;
  let activeIntersections = 0;
  for (const log of discHistory) {
    activeIntersections += log.startEnd;
    if (log.startEnd > 0) intersections += activeIntersections - 1;
    if (intersections > 10000000) return -1;
  }
  return intersections;
}

class DiscLog {
  constructor(x, startEnd) {
    this.x = x;
    this.startEnd = startEnd;
  }
}

function compare(a, b) {
  return a.x !== b.x ? a.x - b.x : b.startEnd - a.startEnd
}


console.log(solution([1, 5, 2, 1, 4, 0]));   // 11

 

 

 

 

 

 

Prefix Sums

 

Q. Passing Cars

 

function solution(A) {
  let suffixSum = new Array(A.length + 1).fill(0);
  let count = 0;
  for (let i = A.length - 1; i >= 0; i--) {
    suffixSum[i] = A[i] + suffixSum[i];
    if (count > 1000000000) return -1;
  }
  return count;
}


console.log(solution([0, 1, 0, 1, 1]));

 

 

 

 

 

 

Q. Div Count Problem

 

function solution(A, B, K) {
  let nStart = Math.ceil(A / K);
  let nEnd = Math.floor(B / K);
  return nEnd - nStart + 1
}

console.log(solution(6,11,2))