백준 - 11728 배열 합치기

문제

정렬되어있는 두 배열 A와 B가 주어진다. 두 배열을 합친 다음 정렬해서 출력하는 프로그램을 작성하시오.

입력

• 첫째 줄
  • 배열 A의 크기 N
  • 배열 B의 크기 M
• 둘째 줄
  • 배열 A의 내용
• 셋째 줄
  • 배열 B의 내용

제한조건

• 1 ≤ N, M ≤ 1,000,000
• 배열에 들어있는 수는 절댓값이 109보다 작거나 같은 정수

출력

첫째 줄에 두 배열을 합친 후 정렬한 결과를 출력한다.

예시

// NOTE: 입력
4 3
2 3 5 9
1 4 7

// NOTE: 출력
1 2 3 4 5 7 9

해결

- a 배열과 b 배열은 이미 정렬이 되어있음
- pointer 개념을 가져와야함
- a[pointer]와 b[pointer]를 비교

필요한 변수

• 합병정렬을 담아낼 배열
• a 배열의 pointer
• b 배열의 pointer

javascript는 pointer 개념이 없으니까 index를 이용할거임

합병정렬

• 두 pointer(index가 될 변수) 초기값을 0으로 설정
• 반복문
  • pointer가 각각 N 또는 M 보다 작을 때에만 반복
    • a 배열이 모두 소진된 경우
      • b 배열에서 pointer가 가리키는 요소(b[pointer])를 합병정렬 배열에 push
    • b 배열이 모두 소진된 경우
      • a 배열에서 pointer가 가리키는 요소(a[pointer])를 합병정렬 배열에 push
    • a[pointer] < b[pointer]인 경우
      • a[pointer]를 push
    • a[pointer] > b[pointer]인 경우
      • b[pointer]를 push
  • push 하고나서 pointer를 옮겨줘야 함
    • pointer++

전체 코드

const solution = () => {
    const [[N, M], _aArr, _bArr] = require('fs')
    .readFileSync('dev/stdin')
    .toString()
    .trim()
    .split('\n')
    .map(v => v.split(' ').map(v => +v));
    
    let _mergeSortArr = [];
    let _a_idx = 0;
    let _b_idx = 0;
    while(_a_idx < N || _b_idx < M) {
        // NOTE: a 배열이 모두 소진된 경우
        if (_a_idx === N) {
            _mergeSortArr.push(_bArr[_b_idx++]);
            continue;
        }
        
        // NOTE: b 배열이 모두 소진된 경우
        if (_b_idx == M) {
            _mergeSortArr.push(_aArr[_a_idx++]);
            continue;
        }
        
        // NOTE: a배열[idx] < b배열[idx]인 경우
        if (_aArr[_a_idx] < _bArr[_b_idx]) {
            _mergeSortArr.push(_aArr[_a_idx++]);
            continue;
        }
        
        // NOTE: a배열[idx] > b배열[idx]인 경우
        _mergeSortArr.push(_bArr[_b_idx++]);
    }
    
    console.log(_mergeSortArr.join(' '));
};

solution();

---

출처

백준 11728번: 배열 합치기