백준: 좌표 압축(18870)

알고리즘 문제 해결 과정을 기록합니다

September 22, 2025 · 3 min read

문제 개요 #

Source: 백준 링크
Difficulty: Silver 2
Key Concept: 정렬

접근 방법 #

해당 문제는 숫자 배열을 입력받고 해당 수보다 작은 배열 안의 수의 개수를 출력하는 문제였습니다. 그래서 먼저 원본과 정렬을 할 배열이 필요하므로 2개의 배열에 수를 집어 넣은 다음 하나만 정렬하도록 하였습니다. 이후 중복을 없앤 다음 iterator를 이용하여 해당 수의 위치를 find로 찾은 다음 begin을 빼주어 출력하도록 하였습니다.

시행착오 #

처음 vector 2개를 이용해서 정렬과 iterator를 순회하면서 출음 하는 로직을 사용했을 때는 시간초과가 나버렸습니다. 이는 입력 숫자의 크기가 최대 $10^6$이므로 for문을 순회하면서 find를 하므로 N번 순회하는 동안 각각 N의 시간 복잡도가 발생하므로 $O(N^2)$가 되어버려 최대 $10^{12}$번의 연산이 발생하여 2초 시간 제한인 $2\times 1 \times 10^9$를 대략 $500$배가 되어 있는 즉 1000초가 넘어가는 시간 복잡도를 가지기 때문이었습니다.

해결 방법 #

int n;
void solution(){
    std::cin >> n;
    vector<int> x(n,0);
    for (int i = 0; i < n; i++) {
        std::cin >> x[i];
    }
    vector<int> arr(x.begin(), x.end());
    std::sort(arr.begin(), arr.end());
    arr.erase(std::unique(arr.begin(), arr.end()), arr.end());
    for (int i = 0; i < n; i++) {
        std::cout << std::lower_bound(arr.begin(), arr.end(), x[i])
        - arr.begin()<< " ";
    }
    return 0;
}

알고리즘 설명 #

std::find대신 std::lower_bound를 이용하여서 시간 복잡도를 $O(N\log N)$으로 줄여 문제를 풀 수 있었습니다.

2개의 벡터에 수를 넣고, 정렬한 다음 std::erase를 이용하여 중복을 제거 하여 원본 배열을 순회하면서 std::lower_bound를 이용하면 value보다 크거나 같은 첫 원소를 가리키는 iterator를 반환하기 때문에 동일하게 std::begin()을 빼주면 해당원소의 값 미만인 원소의 개수를 출력할 수 있었습니다.

성능 분석 #

Time Complexity: $O(N\log N)$

핵심 정리 #

이미 정렬되어 있는 배열의 경우 std::lower_bound와 std::begin()을 통해 현재 값보다 미만의 원소들의 개수를 구할 수 있음을 알 수 있었습니다.

또한 std::find와 std::lower_bound의 작동원리도 아래와 같음을 알 수 있었습니다. std::find의 경우 아래 코드와 같이 Linear Search이므로 $O(N)$이라는 시간 복잡도를 가집니다.¹

template<class InputIt, class T = typename std::iterator_traits<InputIt>::value_type>
constexpr InputIt find(InputIt first, InputIt last, const T& value)
{
    for (; first != last; ++first) // first부터 end까지 선형 순회
        if (*first == value)
            return first; // 찾으면 해당 원소를 가리키는 iterator 반환

    return last; // 못 찾으면 end() 반환
}

std::lower_bound의 경우 아래 코드와 같이 Binary Search를 사용하여 $O(\log N)$을 시간 복잡도로 가집니다.²

template<class ForwardIt, class T = typename std::iterator_traits<ForwardIt>::value_type>
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value)
{
    return std::lower_bound(first, last, value, std::less{});
}

이 때 std::less{}는 아래와 같은 의미를 지닌 함수 객체입니다.³

constexpr bool operator()(const T& lhs, const T& rhs) const
{
   return lhs < rhs; // assumes that the implementation handles pointer total order
}

template<class ForwardIt, class T = typename std::iterator_traits<ForwardIt>::value_type,
         class Compare>
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp)
{
    ForwardIt it;
    typename std::iterator_traits<ForwardIt>::difference_type count, step;
    count = std::distance(first, last);

    while (count > 0)
    {
        it = first;
        step = count / 2;
        std::advance(it, step);

        if (comp(*it, value))
        {
            first = ++it;
            count -= step + 1;
        }
        else
            count = step;
    }

    return first;
}

Pelikan's Glide