본문 바로가기
알고리즘

[백준 11728] 알고리즘 108일차 : 배열 합치기

by SiO2whocode 2021. 7. 23.
반응형

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

 

11728번: 배열 합치기

첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거

www.acmicpc.net

C++ 투포인터 

투포인터문제인데 전의 유형들과는 다른 문제

정렬되어 있는 두 배열을 하나의 정렬된 배열로 (정렬 알고리즘을 쓰지 않고) 합치는 문제

이걸 1학년때 프로그래밍 과목 과제로 나왔었다. 정말 똑같음

 

접근방법

두개의 배열을 합치는데 배열 당 하나씩 포인터를 갖는다.

정렬되어있는 배열이라고 했으므로 앞부터 하나씩 비교해서 작은 값을 결과 배열에 넣으면된다.

 

오답노트

시간초과 나서 앞에 sync with stdio false, cin tie 끊어줬다

 

소스코드

#include <iostream>
using namespace std;

int main(){
	ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    //init & input
    int an, bn, cn;
    cin >> an >> bn;
    cn = an + bn;
    
    int A[an], B[bn], C[cn];
    for(int i = 0 ; i < an ; i++){
        cin >> A[i];
    }
    for(int i = 0 ; i < bn ; i++){
        cin >> B[i];
    }
    
    //process
    int a,b,c;
    a = b = c = 0;
    while(a < an && b < bn){
        if(A[a] <= B[b]){
            C[c++] = A[a++];
        }else{
            C[c++] = B[b++];
        }
    }
    
    while(a < an){
        C[c++] = A[a++];
    }
    while(b < bn){
        C[c++] = B[b++];
    }
    
    //output
    for(int i = 0 ; i < cn ; i++){
        cout << C[i] << " ";
    }
    cout << "\n";
    
    return 0;
}
반응형

댓글0