[백준][C++] 24060번 : 알고리즘 수업 - 병합 정렬 1

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

24060번: 알고리즘 수업 - 병합 정렬 1

 

 

 

---

- 문제

 

  문제에서 주어진 함수를 활용하여 문제를 해결하면 된다.

 

 

---

- 해설

 

  문제에서 merge_sort와 merge가 주어졌으므로 이를 활용하여 저장 횟수에 맞는 결과를 출력하면 된다. 

 

출력 횟수를 count하는 전역변수를 하나 만들고, 함수 안에 k를 하나 더 추가해서 비교를 하도록 한다.

 

 

---

- 풀이

 

#include <iostream>

using namespace std;
int inputcnt = 0;

void merge(int *s, int p, int q, int r, int k)
{
    int i = p, j = q + 1, t = 1;
    int tmp[r + 2];
    while (i <= q && j <= r)
    {
        if (s[i] <= s[j])
        {
            tmp[t++] = s[i++];
        }
        else
        {
            tmp[t++] = s[j++];
        }
    }
    while (i <= q)
    {
        tmp[t++] = s[i++];
    }
    while (j <= r)
    {
        tmp[t++] = s[j++];
    }
    i = p;
    t = 1;
    while (i <= r)
    {
        s[i++] = tmp[t++];
        if (++inputcnt == k)
            cout << tmp[t - 1];
    }
}

void merge_sort(int *s, int p, int r, int k)
{
    int q;
    if (p < r)
    {
        q = (p + r) / 2;
        merge_sort(s, p, q, k);
        merge_sort(s, q + 1, r, k);
        merge(s, p, q, r, k);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int p[500002];
    int N, K;
    cin >> N >> K;
    for (int i = 0; i < N; i++)
    {
        cin >> p[i];
    }
    merge_sort(p, 0, N - 1, K);
    if (inputcnt < K)
    {
        cout << -1;
    }
    return 0;
}

---

- 새롭게 알게 된 점

 

X