[백준] 11728번 배열 합치기

 

 

문제

소스코드

 

#include<iostream>
#include<set>
int main() {
 
    //입출력 속도 상승
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
 
    int N, M;
    std::multiset<int> set;
    std::cin >> N >> M;
 
    for (int i = 0; i < N; ++i) {
        int value;
        std::cin >> value;
        set.insert(value);
    }
    for (int i = 0; i < M; ++i) {
        int value;
        std::cin >> value;
        set.insert(value);
    }
 
 
    for (const auto& i : set)
        std::cout << i <<" ";
}

 

 

후기

이 문제는 투 포인터를 사용하거나 정렬을 사용해서 푸는 문제이다.

정렬도 기본 sort() 알고리즘을 사용하면 시간 초과에 걸릴 것이다. 왜냐하면 거의 다 정렬된 정렬에는 최악의 복잡도를 보여주기 때문에 병합 정렬을 사용해야 할 것이다.

나는 STL컨테이너에 multiset이 정렬이 된다는 특징을 가지고 처음에 두 개의 배열로 따로 받는 게 아닌 하나의 multiset으로 받아서 정렬되도록 문제를 풀었다. 컨테이너의 특징을 잘 알고 있다면 이러한 방법으로도 풀 수 있다 

 

여담으로 C#으로 풀기위해서 시도한 문제 인대 C#은 시간 초과가 발생해서 C++로 풀었다.

 

using System;
using System.Text;
using System.Collections.Generic;
 
 
namespace 씨샵
{
    class 배열합치기
    {
        static void Main(string[] args)
        {
            SortedSet<int> set = new SortedSet<int>();
 
            //처음 배열 크기
            Console.ReadLine();
 
            string a = Console.ReadLine();
            string[] s = a.Split();
 
            foreach (var i in s)
                set.Add(Int32.Parse(i));
 
            a = Console.ReadLine();
            s = a.Split();
 
            foreach (var i in s)
                set.Add(Int32.Parse(i));
 
 
            foreach (var i in set)
                Console.Write(i + " ");
 
        }
    }// end of class
} //end of namespace
 

불필요하게 split하는거 때문에 시간 초과가 발생하는 거 같은데 이러한 입력을 원하는 문제에서는 어떻게 받아야 할지 아직 잘 모르겠다.

 

 

출처 및 레퍼런스

문제 링크: 11728번: 배열 합치기 (acmicpc.net)