알고리즘 문제풀이
[백준 11728] 알고리즘 108일차 : 배열 합치기
SiO2whocode
2021. 7. 23. 11:22
728x90
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;
}
728x90