99. 이것이 코딩 테스트다 6장 : 두 배열의 원소 교체 Javascript

1. 문제에 대한 이해

• 우리가 풀어야 할 문제는 무엇인가?
   - 배열 A의 모든 원소의 합의 최대값을 구하라
• 주어진 자료는 무엇인가?
   - N개의 원소
   - K번의 바꿔치기
   - 배열 A
   - 배열 B

2. 계획

• 전에 비슷한 문제를 알고 있는가?
• 이 문제를 푸는데 있어서 유용하게 쓸 수 있는 지식은 무엇인가?

1. 배열 A의 최소값을 구한다
2. 배열 B의 최대값을 구한다
3. 서로 바꾸고 count +1을 해준다
4. count 값이 K가 될때까지 반복한다.

3. 실행

• 풀이 계획을 실행하고, 각 단계가 올바른지 점검하라.
  

첫번째 풀이

const solution = (K, A, B, count = 0) => {
  // count 값이 K가 될때까지 반복한다.
  if (count === K) {
    return A.reduce((acc, cur) => acc + cur, 0);
  }

  // 배열 A의 최소값을 구한다 O(N)
  let minA = Math.min(...A);
  // 배열 B의 최대값을 구한다 O(M)
  let maxB = Math.max(...B);
  // 서로 바꾸고 count + 1을 해준다
  // 최소값과 최대값의 위치를 모름
  let minAIndex = A.indexOf(minA); // O(N)
  let maxBIndex = B.indexOf(maxB); // O(M)

  // A[minAIndex]에 maxB를 쓴다.
  A[minAIndex] = maxB  // O(1)
  // B[maxBIndex]에 minA를 쓴다.
  B[maxBIndex] = minA  // O(1)

  return solution(K, A, B, count + 1);
  };

4. 반성

• 첫번째 풀이처럼 풀면 시간 복잡도가 O((N+M) * K)다. 그래서 효율성이 떨어지기 때문에 다른 방법으로 풀어봤다.
• 배열을 한번만 정렬해두면 값을 쓰고 삭제하는 부분이 O(1)이기 때문에 첫번째 풀이보다 훨씬 효율성이 좋아진다.

두번째 풀이

const solution = (K, A, B, count = 0) => {
  if (count === K) {
    return A.reduce((acc, cur) => acc + cur, 0);
  }

  let sortA = A.sort((a, b) => a - b);
  let sortB = B.sort((a, b) => a - b);

  sortA[0] = sortB[sortB.length - 1];
  sortB.pop();
  
  return solution(K, sortA, sortB, count + 1);
};

test('sumArr', () => {
  expect(solution(3, [1, 2, 5, 4, 3], [6, 7, 8, 9, 10])).toEqual(8 + 9 + 10 + 5 + 4);
  expect(solution(3, [1, 2, 5, 4, 3], [1, 1, 1, 1, 1])).toEqual(1 + 2 + 3 + 4 + 5);
  expect(solution(3, [1, 2, 5, 4, 3], [2, 2, 2, 2, 2])).toEqual(2 + 2 + 3 + 4 + 5);

});