[백준 11728] 배열 합치기 (C#, C++) - soo:bak

문제 링크

11728번 - 배열 합치기

설명

이미 오름차순으로 정렬되어 있는 두 배열 A, B가 주어질 때, 두 배열을 합친 뒤 오름차순으로 출력하는 문제입니다.

접근법

두 배열이 이미 정렬되어 있으므로, 다시 전체 정렬을 할 필요는 없습니다. 두 배열의 현재 위치를 가리키는 포인터를 하나씩 두고 더 작은 값을 결과로 보내면 됩니다.

현재 A[i]와 B[j]를 비교해서 더 작은 값을 출력하고 해당 포인터를 한 칸 이동합니다. 한쪽 배열을 모두 사용했다면, 나머지 배열의 원소를 그대로 이어서 출력하면 됩니다.

---

Code

C#

using System;
using System.IO;

class FastScanner {
  private readonly Stream _stream = Console.OpenStandardInput();
  private readonly byte[] _buffer = new byte[1 << 16];
  private int idx;
  private int size;

  private int Read() {
    if (idx >= size) {
      size = _stream.Read(_buffer, 0, _buffer.Length);
      idx = 0;
      if (size == 0)
        return -1;
    }
    return _buffer[idx++];
  }

  public int NextInt() {
    int c = Read();
    while (c <= 32) {
      c = Read();
    }

    int sign = 1;
    if (c == '-') {
      sign = -1;
      c = Read();
    }

    int value = 0;
    while (c > 32) {
      value = value * 10 + (c - '0');
      c = Read();
    }
    return value * sign;
  }
}

class Program {
  static void Main() {
    var fs = new FastScanner();
    int n = fs.NextInt();
    int m = fs.NextInt();

    int[] a = new int[n];
    int[] b = new int[m];

    for (int i = 0; i < n; i++)
      a[i] = fs.NextInt();
    for (int i = 0; i < m; i++)
      b[i] = fs.NextInt();

    using var output = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));

    int ai = 0;
    int bi = 0;
    bool first = true;

    while (ai < n && bi < m) {
      int value;
      if (a[ai] <= b[bi]) value = a[ai++];
      else value = b[bi++];

      if (!first)
        output.Write(' ');
      first = false;
      output.Write(value);
    }

    while (ai < n) {
      if (!first)
        output.Write(' ');
      first = false;
      output.Write(a[ai++]);
    }

    while (bi < m) {
      if (!first)
        output.Write(' ');
      first = false;
      output.Write(b[bi++]);
    }

    output.WriteLine();
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m;
  cin >> n >> m;

  vector<int> a(n), b(m);
  for (int i = 0; i < n; i++)
    cin >> a[i];
  for (int i = 0; i < m; i++)
    cin >> b[i];

  int ai = 0;
  int bi = 0;
  bool first = true;

  while (ai < n && bi < m) {
    int value;
    if (a[ai] <= b[bi]) value = a[ai++];
    else value = b[bi++];

    if (!first)
      cout << ' ';
    first = false;
    cout << value;
  }

  while (ai < n) {
    if (!first)
      cout << ' ';
    first = false;
    cout << a[ai++];
  }

  while (bi < m) {
    if (!first)
      cout << ' ';
    first = false;
    cout << b[bi++];
  }

  cout << "\n";

  return 0;
}