[백준(BOJ)] 11728번 : 배열 합치기 - C++[CPP]

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

11728번: 배열 합치기

 

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 정렬
• 두 포인터

 

---

 

⊙ 문제 접근 과정

 

문제에서 KeyPoint를 찾았는가?

 

 

KeyPoint: 정렬되어 있는

 

정렬이 이미 되어있다. 그렇다면 인덱스만을 이용하여 문제를 풀 수 있지 않을까?

 

처음에는 "정렬되어 있는"을 무시하고 문제를 풀었는데 시간 초과가 떴다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n,m;

int main() {
    cin>> n >> m;
    
    int a[n+1],b[m+1];
    vector<int> c;

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

    for(int i=0;i<n;i++) {
        c.push_back(a[i]);
    }
    for(int i=0;i<m;i++) {
        c.push_back(b[i]);
    }

    sort(c.begin(),c.end());

    for(int i=0;i<n+m;i++) {
        cout<<c[i]<<" ";
    }
}

 

그냥 하나의 벡터에 다 넣어버리고 정렬을 돌린 코드다.

 

그 다음 시도는 그냥 배열이나 벡터를 추가적으로 더 생성하지 않고 바로 출력하는 쪽으로 코드를 짰다.

 

---

⊙ 문제 풀이

 

#include <iostream>

using namespace std;

int n,m;
int a_index=0, b_index=0;

int main() {
    ios_base::sync_with_stdio(0); 
    cin.tie(0); 
    cout.tie(0);

    cin >>n>>m;

    int a[n+1],b[m+1];

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

    while(a_index < n && b_index < m) {
        if(a[a_index]<=b[b_index]) {
            cout << a[a_index++] << " ";
        } else {
            cout << b[b_index++] << " ";
        }
    }
    while(a_index<n) {
        cout << a[a_index++] << " ";
    }
    while(b_index<m) {
        cout << b[b_index++] << " ";
    }
}

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

좋아요는 로그인하지 않아도 누를 수 있습니다!