9 / 29

📚 문제

---

두 배열 합치기

오름차순으로 정렬이 된 두 배열이 주어지면 두 배열을 오름차순으로 합쳐 출력하는 프로그램을 작성하세요. 첫번째 줄에 첫번째 배열의 크기 n이 주어진다. 두번째 줄에 n개의 배열 원소가 오름차순으로 주어진다. 세번째 줄에 두번째 배열의 크기 m이 주어진다.
네 번째 줄에 M개의 배열 원소가 오름차순으로 주어진다. 각 리스트의 원소는 int형 변수의 크기를 넘지 않는다.

sort를 사용하게 되면 시간 복잡도가 n log n이 된다 . 따라서 sort를 사용하지 않고 풀어보자

스스로 해결 여부
❌

🔍 문제 접근

---

한시간 정도 혼자 풀다가 잘못풀었다는것을 알고 강의를 보고 다시 풀었다 😅

• 처음 내가 접근했던 방법

1. 1씩 증가하는 i를 통해 반복문을 만든다. i는 두 배열중 길이가 작은 배열의 길이만큼 값이 증가한다.
2. 각각 두 배열의 i번째를 비교해서 만약 arr1[i]값이 arr2[i]보다 작거나 같으면 빈 배열에 arr1[i]를 먼저 넣고, arr2[i]값을 그 뒤에 넣는다. 그 반대의 경우라면 arr2[i]의 값을 먼저 넣고, arr1[i]을 넣는다.
3. 그 다음 길이가 긴 배열의 남은 요소드을 그 뒤에 붙여준다.
4. 이것을 n < m 일때의 경우와, n > m 일때의 경우로 나누어서 작업해줌.
5. 될 것같았으나 완전 잘못 접근함.. 밑에 코드를 보면 알 수 있다.

const getOneArray = (n, arr1, m, arr2) => {
  let result = []
  // n이 m보다 작을때
  if (n <= m) {
    for (let i = 0; i < n; i++) {
      if (arr1[i] <= arr2[i]) {
        result.push(arr1[i])
        result.push(arr2[i])
      } else {
        result.push(arr2[i])
        result.push(arr1[i])
      }
    }
    for (let j = n; j < m; j++) {
      result.push(arr2[j])
    }
    return result
    // m이 n보다 작을때
  } else {
    for (let i = 0; i < m; i++) {
      if (arr1[i] <= arr2[i]) {
        result.push(arr1[i])
        result.push(arr2[i])
      } else {
        result.push(arr2[i])
        result.push(arr1[i])
      }
    }
    for (let j = m; j < n; j++) {
      result.push(arr1[j])
    }
    return result
  }
}

console.log(getOneArray(3, [1, 3, 5], 5, [2, 3, 6, 7, 9]))
// [ 1, 2, 3, 3, 5, 6, 7, 9 ]
console.log(getOneArray(4, [1, 3, 5, 10], 5, [2, 3, 6, 7, 9]))
// [ 1, 2, 3, 3, 5, 6, 7, 10, 9 ] <= 이 테스트에서 오류가 나는것을 볼 수 있다.
console.log(getOneArray(5, [2, 3, 6, 7, 9], 3, [1, 3, 5]))
// [ 1, 2, 3, 3, 5, 6, 7, 9 ]

👩🏻‍💻 코드

---

• 강의를 보고 다시 푼 방법

1. two pointers라는 알고리즘으로 각 배열의 포인터를 정해주고(포인터는 인덱스를 의미하는 숫자가 됨) 각각의 포인터가 어떤 조건을 만족시킬때마다 증가시킨다.
2. 이번 문제에서는 p1, p2 변수를 두어서 각 배열의 포인터를 각각 분리해준다. 0부터 시작한다.
3. 이 포인터는 배열의 길이보다 작다. 두 배열의 길이가 다르기 때문에 조건을 나누어줄것이다.
4. 각 포인터가 두 배열의 크기보다 작을때를 둘다 만족할 때의 경우 만약 arr1[p1]이 arr[p2]보다 작으면 result에 arr1[p1]을 넣어주고 포인터에 1을 증가시킨다. 왜냐면 그래야 다음 포인터가 가리키는 값이랑 비교를 할 수 있기 때문!!
5. 이렇게 비교를 하면서 작은 값을 result에 넣어주고, 어떤 포인터의 값이 끝나면 조건을 만족시키지 않을 것이다. 그럼 남은 배열의 값들을 그대로 넣어주어야 하기 때문에 밑에 조건을 추가해준다.
6. 그리고 result값을 리턴해주면 끝!
7. 배열에서 인덱스 값에 접근할때 그 안의 변수를 넣은뒤 증가 시키는 방법을 새롭게 알게되었다.

const getOneArray = (n, arr1, m, arr2) => {
  let result = []
  let p1 = 0
  let p2 = 0
  while (p1 < n && p2 < m) {
    if (arr1[p1] <= arr2[p2]) {
      result.push(arr1[p1++])
    } else {
      result.push(arr2[p2++])
    }
  }
  while (p1 < n) {
    result.push(arr1[p1++])
  }
  while (p2 < m) {
    result.push(arr2[p2++])
  }
  return result
}

console.log(getOneArray(3, [1, 3, 5], 5, [2, 3, 6, 7, 9])) 
// [ 1, 2, 3, 3, 5, 6, 7, 9 ]
console.log(getOneArray(4, [1, 3, 5,10], 5, [2, 3, 6, 7, 9]))
// [ 1, 2, 3, 3, 5, 6, 7, 9, 10 ]
console.log(getOneArray(5, [2, 3, 6, 7, 9],3, [1, 3, 5] ))
// [ 1, 2, 3, 3, 5, 6, 7, 9 ]