2548번

2548번 - 대표 자연수

N제한이 2만이고 이중 포문으로 풀었기 때문에 시간초과가 발생하지 않을까 했는데 발생하지 않았다..

그래서 다른 분들 코드를 보니까 엄청 간단하게, 정렬후 중간값보다 조금 작은 값으로 하는데 잘 이해가 가지 않았다.

그래서 백준 SLACK 을 통해서 물어보니 

y = |x-1| + |x-3| + |x-6| 의 그래프를  x=3 일때 최소값이다는 것을 생각해보라는 갓님의 말... 한방에 이해가 갔다.

문제 푸는 속도가 굉장히 많이 차이가 났다..

<정답 코드>

#include<iostream>
#include<algorithm>
using namespace std;
 
int n, ans, MIN = 1987654321;
int num[20001];
int main(int argc, char** argv)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
 
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> num[i];
    }
    
    sort(num, num + n);
 
    if (n % 2 == 0)
    {
        cout << num[(n / 2) - 1];
    }
    else
    {
        cout << num[n / 2];
    }
 
    
    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

<정답 코드 - 이중 포문>

#include<iostream>
#include<algorithm>
using namespace std;
 
int n, ans, MIN = 1987654321;
int num[20001];
int main(int argc, char** argv)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
 
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> num[i];
    }
    
    sort(num, num + n);
 
    for (int i = 0; i < n; i++)
    {
        if (num[i] != num[i + 1] || i == n - 1)
        {
            int sum = 0;
            for (int j = 0; j < n; j++)
            {
                sum += abs(num[i] - num[j]);
            }
 
            if (sum < MIN)
            {
                MIN = sum;
                ans = num[i];
            }
        }
    }
 
    cout << ans;
 
    
    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}