[Baekjoon/백준] 11728번: 배열 합치기_merge(C/C++) / (알게된 점 多)

 

이번 문제는 문제 난이도 자체는 평이, 아니 쉬운 수준이었다.

그냥 배열을 합치고 algorithm 헤더의 sort만 해주면 끝나는 문제였다.

문제는 다름이 아니라 시간초과 발생 때문에 대략 2시간을 잡아먹은 것이다.

코드의 길이를 정말 최대로 줄일 수 있을만큼 줄이고 vector도 사용해보고 배열도 사용해 보았다.

하지만 그렇게 짜본 코드가 모두 시간초과가 떠버렸다.

 

결과적으로 위에 내가 짰던 코드가 틀린 것은 아니지만,

키워드 3줄만 적어주었더니 시간초과가 뜨지 않았다.

 

 

 

 

※ 이번 문제에서 알게된 점

§  ios_base::sync_with_stdio() 함수

먼저 C++의 <iostream>은 C의 <stdio.h>와 다르다. 

C++의 입출력 작업 시, C의 입출력과 동기화 되도록 설계되어 상당히 느린 입출력과정을 겪는다.

추가적으로 endl도 출력문자 출력+출력buffer를 함께 비워 시간이 많이 걸려 \n사용을 권장한다.

이때 말하는 "동기화"를 뜻하는 코드가 ios_base::sync_with_stdio이고, 이 동기화를 풀어주는 코드이다.

따라서 동기화가 풀어진다면?  => 당연히 속도를 올릴 수 있다!

ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

 

큰 힘에는 큰 책임이 따른다고, 이런 ios_base::sync_with_stdio에도 치명적인 단점이 있다.

 

1. 그건 바로 싱글 쓰레드 (single thread) 환경은 괜찮지만, 멀티 쓰레드 (Multi Thread)환경에서는 출력순서가 어그러진다.

즉, 멀티쓰레드 환경에서의 출력순서가 보장될 수 없다는 것이다!

cf-1) 코딩테스트에서는 싱글쓰레드만 사용하기에 사용해도 무방하다.

cf-2) 다만 실무에서는 ios_base::sync_with_stdio를 쓰기보단, 속도를 올리기 위해 C입출력 방식을 권장한다.

 

 

2. 버퍼가 분리되었기에 cin과 scanf, gets, getchar 등의 C문법 (당연히 출력코드도 동일)을 같이 사용할 수 없다!

 

cf-2) 싱글, 멀티쓰레드란? https://chan4im.tistory.com/35

this->OS.code(4)

 

 

 

§  cin.tie(NULL)  /  cout.tie(NULL) 함수

[정의]: istream, ostream 즉, stream을 untie 하여 자동으로 입출력 버퍼를 비우지 않게 함

cin과 cout간의 tie를 끊어주는, 즉 다른 입출력이 온다면 기존의 입출력을 비워주도록 하는 것이다.

이 tie를 끊어줌으로써 시간을 많이 절감할 수 있다.

 

[예시]

왼쪽그림에서 ios_base::sync_with_stdio(0);을 지워도 console창은 하게 뜬다.

왼쪽을 보면 cout으로 "입력"이란 문구가 출력된 후 cin이 나오는 것을 알 수 있고, 이는 익숙한 방식이다.

하지만 우측은 입력 후 출력이 모두 동시에 되는 것을 알 수 있다.

우리가 tie를 끊어서 입력 전에 출력관련 문구가 아무리 입력보다 먼저 적혀있었더라도 출력이 되지 않는다.

만약 입력전에 출력되게 하고 싶다면 cout buffer를 수동적으로 비워줘야 한다.

 

https://hegosumluxmundij.tistory.com/54

 

 

 

 

 

 

 

§ reserve() 와 resize() 의 차이

가장 고생했던 부분이 있는데 다음과 같다.

https://hoondev.tistory.com/7

§ reserve() 와 resize() 의 차이

capacity: 미리 할당해놓은 배열공간

size: 배열에 들어있는 원소의 수

 

대부분의 컨테이너 STL 자료구조들은 일정 크기를 할당(capacity)한 후 

size가 capacity를 넘으면 2배정도의 크기를 늘려 이동하는 방식으로 구현되어 있다.

 

§ reserve(N)

- vector의 capacity를 N으로 설정하는 것.

- N이 현재 capacity보다 클 때만 작동, 작으면 아무 일도 발생X

- N이 현재 capacity보다 크다면 모든 원소 reference와 iterator가 전부 무효화(invalidate)된다.

 

§ resize(N)   /   resize(N, value)

- size > N인 경우, 원소의 개수를 줄인다.

- size < N인 경우, 입력된 value가 없으면 default값인 0으로 할당한다. 있다면 value로 할당.

  그 후, size가 N이 되도록 늘린다.

 

 

 

 

 

 

§ my solution 

총 3가지 방식으로 해결하였다.

1. 배열과 배열의 포인터(주소값)로 sort 후 해결 (메모리 9708KB  /  시간 636ms)

#include <iostream>
#include <algorithm>
using namespace std;

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

    int N, M;   cin >> N >> M;
    int arr[N+M];

    for (int i = 0; i < N+M; i++) {
        cin >> arr[i];
    }
    sort(arr, arr+N+M);

    for (const auto& x:arr) {
        cout << x << " ";
    }
}

 

2. 배열을 벡터로만 바꿈 (메모리 9836KB  /  시간 688ms)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    int N, M;   cin >> N >> M;
    vector<int> v(N+M);
    for (int i = 0; i < N+M; i++)
        cin >> v[i];

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

    for (int i = 0; i < N+M; i++) {
        cout << v[i] << " ";
    }
}

 

3. 정말 벡터 2개를 생성, 합친 후 정렬! (메모리 17656KB  /  시간 644ms)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    int N, M;   cin >> N >> M;
    vector<int> v1(N);
    vector<int> v2(M);

    for (int i = 0; i < v1.size(); i++){
        cin >> v1[i];
    }
    for (int i = 0; i < v2.size(); i++){
        cin >> v2[i];
    }

    vector<int> v3;

    v3.reserve(v1.size() + v2.size());
    v3.insert(v3.end(), v1.begin(), v1.end());
    v3.insert(v3.end(), v2.begin(), v2.end());

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

    for (const auto& x:v3) {
        cout << x << " ";
    }
}

 

4. 2개의 vector를 merge와 sort를 이용해 정렬(메모리 24684KB  /  시간 544ms)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    vector<int> v1;
    vector<int> v2;

    int N, M;   cin >> N >> M;

    for (int i = 0; i < N; i++) {
        int num;    cin >> num;
        v1.push_back(num);
    }
    for (int i = 0; i < M; i++) {
        int num;    cin >> num;
        v2.push_back(num);
    }
    vector<int> v3;

    merge(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(v3));

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

    for (const auto& x:v3) {
        cout << x << " ";
    }
}