[백준 BOJ] 11728번 배열 합치기 (C++/cpp)

문제 설명

https://www.acmicpc.net/problem/11728

11728번: 배열 합치기

 

접근 방법 - 두 포인터의 기본 문제

백준의 11728번 문제는 두 포인터의 원리를 이용하여 해결해야 하는 기초 문제이다.

해당 문제는, 입력값으로 나오는 2개의 배열을 합친 형태를 오름차순으로 출력해야 하는 문제이다.

사실 일부 언어에서는 정말 배열 2개를 그대로 합친 뒤에 정렬을 수행하면 해결될 문제이긴 하다.

다만, 알고리즘 분류에도 두 포인터 개념이 있기 때문에 필자는 이를 이용하여 해결을 시도해보았다.

여기서 필자가 겪어본 두 포인터란, 2개의 변수를 통해 배열의 인덱스를 가리키는 원리를 이용한 알고리즘인 것으로 보인다. (자세한 내용은 해당 블로그에 포스팅할 예정이다.)

혹여나 이 원리에 익숙하지 않거나 해당 문제를 해결하는 데에 어려움을 겪고 있다면, 아래의 설명과 코드를 참고해보길 바란다.

특히나 시간 초과로 애먹고 있다면 특히나 아래를 참고하길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 배열의 값을 입력받을 공간(arr)을 전역 변수로 미리 선언해둔다.

 

2) 두 배열의 크기(n1, n2)를 입력받으며, 첫 번째 배열의 값들을 arr에 우선적으로 받아둔다.

 

3) arr의 인덱스를 나타낼 변수 p1을 0으로 초기화하여 선언한다.

 

4) n2의 크기만큼 반복문을 실행하여 아래의 연산을 취한다.

- 두 번째 배열의 값(a)을 하나씩 입력받는다.

- 현재 arr에 있는 a보다 작은 값들을 p1을 통해 모두 순차적으로 출력한 뒤, 그 뒤에 a를 출력한다.

이때, p1의 값은 늘 첫 번째 배열의 크기인 n1보다 반드시 작아야 한다.

- a를 통해 두 번째 배열의 마지막 값을 출력할 때까지 해당 연산을 반복한다.

첫 번째 배열과 두 번째 배열의 크기 최댓값은 각각 100만이다.
따라서 두 배열의 값들을 모두 입력받은 뒤에 연산을 수행하면, 연산할 것이 너무 많아 시간 초과가 걸린다.
(실제로 필자도 이렇게 했다가 시간 초과가 났다.)
그래서 필자는 두 번째 배열에선 입력과 연산 및 출력을 동시에 하게끔 하여 총 실행시간을 줄여보았다.

 

5) 만일 위 반복문이 종료되어도 arr에 출력되지 못한 값이 남아있다면 다시 반복문을 만들어 모두 출력되도록 한다.

 

6) 출력이 모두 완료되었다면, 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#define endl '\n'
using namespace std;

//백준 11728번 코드
int arr[1000001];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);   cout.tie(NULL);

    int n1, n2;
    cin >> n1 >> n2;
    for (int i = 0; i < n1; i++) {
        cin >> arr[i];
    }
    
    int p1 = 0;
    for (int i = 0; i < n2; i++) {
        int a;
        cin >> a;
        while (p1 < n1 && a > arr[p1]) {
            cout << arr[p1] << " ";
            p1++;
        }
        cout << a << " ";
    }

    while (p1 < n1) {
        cout << arr[p1] << " ";
        p1++;
    }

    cout << endl;
}

 

제출 결과

(2022.08.21 백준 11728번 문제 제출 결과)