18310번 안테나

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

# 복습 # 추천 # 필수 # 코딩 # 코테 # 구현 # 생각 # 이분 탐색 # 중앙값 # 정렬

Greedy 문제인줄 알았는데

이분 탐색으로 접근했더니 풀렸다.

이 문제는 이분 탐색으로 풀기에는 비효율적이다.

어느 분께서 

처음 회차 이후에는 무조건 앞부분만 보게 되는데 뒷쪽을 탐색하지 않아도 되나요? 

라고 질문을 해주셨는데, 

솔직히 확실하게 알지 못 하여 따로 질문을 통해 알아냈다.

결론은 내 코드가 비효율적이다.

정렬 후 [ {0 + (n - 1)} / 2 ]가 답인데, 내 코드에서는 처음 진행할 시에 Start = 0, End = n - 1 이므로,

mid가 정답과 정확히 일치하는 (n - 1) / 2이기 때문에 그대로 출력되는 것이었다.

질문해주신 분 덕분에 알 수 있었다.

비효율적인 코드

#include <bits/stdc++.h>
 
using namespace std;
 
int n;
vector<int> v;
 
int bt(int Start, int End)
{
    int Left = Start;
    int Right = End;
    int dist = INT32_MAX, ret = 0;
 
    while (Left < Right)
    {
        int mid = (Left + Right) / 2;
        int pivot = v[mid];
        int temp = 0;
 
        for (auto i : v) {
            temp += abs(pivot - i);
        }
 
        // temp가 더 작다면 계속 작게 해줘서 최소의 temp가 될 때까지 진행
        if (temp <= dist) {
            Right = mid - 1;
            ret = pivot;
            dist = temp;
        }
        // temp가 더 크게 나오면 Left를 증가시킨다(다른 경우들이 있는지 파악)
        else {
            Left = mid + 1;
        }
    }
 
    return ret;
}
 
int main()
{
    cin.tie(0);
    scanf("%d", &n);
 
    int input;
    for (int i = 0; i < n; i++) {
        scanf("%d", &input);
        v.push_back(input);
    }
 
    sort(v.begin(), v.end());
 
    printf("%d\n", bt(0, n - 1));
 
    return 0;
}

효율적인 코드

#include <bits/stdc++.h>
 
using namespace std;
 
int n;
vector<int> v;
 
int main()
{
    cin.tie(0);
    scanf("%d", &n);
 
    int input;
    for (int i = 0; i < n; i++) {
        scanf("%d", &input);
        v.push_back(input);
    }
 
    sort(v.begin(), v.end());
 
    printf("%d\n", v[(n - 1) / 2]);
 
    return 0;
}