[BOJ] 백준 2587 대표값2

2587 대표값2

위 문제는 koi 문제 중 초등부 예선에 있는 문제로 대표값 (평균, 중앙값)을 구하는 문제이다.

현재 업무에서 C++을 언어를 주 언어로 하다보니, C++로 모든 것을 연습하고자한다. 따라서 이번 문제도 C++를 보고 풀었으나, 다른 사람들이 푼 소스코드를 보거나, 지식이 부족한 부분에 대해 추가적으로 정리하고자 한다.

문제

대표값2 문제는 초등부 문제로 다소 쉽게 풀 수 있는 문제이다. 자신감을 찾기 위한 문제이기도 하다.

입력으로는 100보다 작은 10의 배수가 5개 들어오며, 평균과 중앙값을 출력하면 된다.

문제 풀이

해당 문제는 단순하게 평균과 중앙값을 출력하면된다.

#include <iostream>
#include <vector>

using namespace std;

int main()
{
  vector<int> v;
  int av = 0;
  for (int i = 0; i < 5; i++) {
    int tmp;
    cin >> tmp;
    v.push_back(tmp);
    av += tmp;
  }

  sort(begin(v), end(v));
  cout << av/5 << endl << v[2] << endl;
}

위의 코드를 보면 쉽게 이해할 수 있다. vector연산을 활용해 값을 순차적으로 입력받는다. 이후 평균값을 위한 값을 순차적으로 더하면 되고, vector 내 존재하는 값을 정렬한 후 가운데 값(평균 값)을 출력하면 된다.

인사이트

이 문제 같은경우 풀이는 간단하다. 다만, 다른사람이 푼 풀이를 보고 이렇게 풀면 좋겠다해서 포스팅을 진행한다.

다른사람코드

#include <cstdio>

int s, t, n=5, c, a[95];
int main() {
  while(n--) scanf("%d", &t), a[t]++, s += t;
  for(t=0; c<3; t++) c += a[t];
  printf("%d\n%d", s / 5, --t);
  return 0;
}

위의 코드에서 중앙값을 구하는 부분을 주의깊게 봐야한다. 카운트 a배열에 입력받은 수를 카운팅하고 for문을 돌면서 카운팅배열을 순차적으로 확인한다. 순차적으로 확인하면서 c 값이 3이 되는 순간 멈춘다. 3이 되는 순간이 “중앙값”이기 때문이다.

위 방식으로 풀게 되면 내가 풀었던 풀이보다 훨씬 효율적이다. 내가 풀었던 풀이로 보게된다면 vector를 사용하기 때문에 소스코드 양이 늘어나게 되고 sorting동작으로 인해 성능이 떨어진다. 백준 문제를 풀때는 위와 같은 문제로 풀는것이 좋을 것 같다.

위의 알고리즘을 활용해 풀 수 있는 문제는 다음과 같다.

• 2576 홀수
• 2592 대표값