[코드트리 조별과제] 중앙값 계산2 C++ 풀이

---

알고리즘 분류

• 정렬
• 문자열

---

문제 설명

n개의 숫자가 주어졌을 때, 순서대로 숫자를 읽다가 홀수 번째의 원소가 주어질 때마다 지금까지 입력받은 값의 중앙값을 출력하는 프로그램을 작성해 보세요. 여기서 중앙값이란, 어떤 주어진 값들을 오름차순으로 정렬했을 때 가장 중앙에 위치하는 값을 의미합니다.

---

입력 설명

첫 번째 줄에는 숫자 n이 주어집니다.
두 번째 줄에는 n개의 숫자가 공백을 사이에 두고 주어집니다.

• 1 ≤ n ≤ 100, n은 홀수
• 0 ≤ 주어지는 숫자 ≤ 100,000

---

출력 설명

n개의 숫자를 순서대로 읽으며 홀수 번째 수를 읽을 때 마다 지금까지 입력받은 값 중 중앙값을 차례대로 공백을 사이에 두고 출력합니다.

---

예제 입력

5
1 2 3 4 5

9
1 5 2 9 7 4 6 10 11

---

예제 출력

1 2 3

1 2 5 5 6

---

아이디어

n번의 숫자를 입력 받으면서 홀수번째 숫자를 입력받을 때마다 입력받은 벡터를 정렬해 주고 그중 중앙값을 출력한다.

---

알고리즘

벡터에 n번의 push_back()연산으로 입력을 받는 도중 홀수번째 숫자를 입력받을 때마다 입력받은 벡터를 오름차순으로 정렬하고 그 중앙값인 vector[vector.size()/2]를 출력한다.

---

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int n;
    cin>>n;
    vector<int> vec;
    for(int i=1;i<=n;i++)
    {
        int temp;
        cin>>temp;
        vec.push_back(temp);
        if(i%2 != 0)
        {
            sort(vec.begin(), vec.end());
            cout<<vec[vec.size()/2]<<" ";
        }
    }
    return 0;
}

 

---

후기

문제 링크 -> https://www.codetree.ai/missions/5/problems/get-median-2?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

난이도가 어려움이어서 약간 겁먹었는데 생각보다 쉽게 풀어서 놀랐다.

---

본 블로그의 모든 글은 개인적인 학습 내용이므로 다양한 오류가 있을 수 있습니다.

오류를 발견하신다면 해당 내용 댓글로 알려주시면 감사하겠습니다!