BOJ - 18870 - 좌표압축

BOJ - 18870 - 좌표압축

문제

---

18870번: 좌표 압축

문제 개념

---

문제를 풀기 앞서 좌표압축이 무엇인지부터 알아야 한다. 좌표압축이란 범위가 광범위한 좌표들이 존재할 때 임시적으로 index값을 매겨 새로운 압축된 좌표를 만드는 것이다.

좌표압축의 처리과정은 다음과 같다.

• x_list [ 2 4 -10 4 -9 ] 의 x축 좌표가 존재할 때 이를 오름차순으로 정리
• [ -10 -9 2 4 4 ] 오름차순으로 정리 후 중복값을 제거
• index [ -10 -9 2 4 ] 중복값 제거 후 인덱스 리스트 생성
  • -10 ~> 0
  • -9 ~> 1
  • 2 ~> 2
  • 4 ~> 3
• CompressList [ 2 3 0 3 1 ] 인덱스 리스트와 x_list를 비교 후 압축좌표 생성

SOL

---

• 좌표 리스트를 오름차순 정리 & 중복 값 제거
• 좌표 압축 인덱스 부여
• 좌표 리스트와 비교 후 인덱스 값 입력 - BinarySearch 사용

구현

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 오름차순 정리(중복 제거)
// 좌표 압축 인덱스 부여 
// 기존 배열과 비교 후 인덱스 값 입력 
// index : 압축좌표 k : 기존 좌표 begin : 압축좌표의 앞단 end : 압축 좌표의 뒷단
int BinarySearch(vector<int> &index, int k, int begin, int end)
{
    if(begin > end) return - 1;
    int m = (begin + end) / 2;
    if(index[m] == k) return m;
    else if(index[m] > k) return BinarySearch(index, k, begin, m-1);
    else return BinarySearch(index, k, m+1, end);
}

int main()
{
    int num, temp;
    vector<int> index;
    vector<int> x_list;
    // 값 입력 
    scanf("%d", &num);
    for(int i=0; i < num; i++)
    {
        scanf("%d", &temp);
        index.push_back(temp);
        x_list.push_back(temp);
    }
    // 오름차순 정렬
    sort(index.begin(), index.end());
    // 중복제거 
    index.erase(unique(index.begin(), index.end()), index.end());
    // index 부여
    for(int i=0; i < x_list.size(); i++)
        x_list[i] = BinarySearch(index, x_list[i], 0, index.size());  
    for(auto el : x_list)
        printf("%d ", el);
    printf("\n");            
}

해설

---

• 좌표 리스트를 오름차순 정리 & 중복 값 제거

  • 오름차순 정렬

    sort(index.begin(), index.end());

  • 중복제거 index.erase(unique(index.begin(), index.end()), index.end());

• 좌표 리스트와 비교 후 인덱스 값 입력 - BinarySearch 사용

    int BinarySearch(vector<int> &index, int k, int begin, int end)
    {
        if(begin > end) return - 1;
        int m = (begin + end) / 2;
        if(index[m] == k) return m;
        else if(index[m] > k) return BinarySearch(index, k, begin, m-1);
        else return BinarySearch(index, k, m+1, end);
    }
      
    	for(int i=0; i < x_list.size(); i++)
    	    x_list[i] = BinarySearch(index, x_list[i], 0, index.size());  
  

• 시간복잡도
  • O(N log N)

다른 풀이

---

과정은 위에 구현해둔 코드와 같으나 이진탐색을 라이브러리로 구현해 둔 lower_bound 를 사용하여 구현 하였다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 오름차순 정리(중복 제거)
// 좌표 압축 인덱스 부여 
// 기존 배열과 비교 후 인덱스 값 입력 
// index : 압축좌표 k : 기존 좌표 begin : 압축좌표의 앞단 end : 압축 좌표의 뒷단

int main()
{
    int num, temp;
    vector<int> index;
    vector<int> x_list;
    // 값 입력 
    scanf("%d", &num);
    for(int i=0; i < num; i++)
    {
        scanf("%d", &temp);
        index.push_back(temp);
        x_list.push_back(temp);
    }
    // 오름차순 정렬
    sort(index.begin(), index.end());
    // 중복제거 
    index.erase(unique(index.begin(), index.end()), index.end());
    // index 부여
    for(int i=0; i < x_list.size(); i++)
        printf("%ld ", (lower_bound(index.begin(), index.end(), x_list[i]) - index.begin()));      
}

lower_bound 사용법

---

• 용도
  • 찾으려는 key 값보다 같거나 큰 수를 찾을 때 사용함.
• 사용 조건
  • 탐색을 진행할 리스트가 오름차순으로 정렬되어 있어야 함.
    • 같거나 큰 수를 찾기 때문.
• lower_bound(리스트의 시작점, 리스트의 끝점, 찾을 key)
  • 반환형은 Iterator(주소 값) 이기에 리스트의 첫 번째 주소를 빼면 N번째 인덱스인지 알 수 있다.
  • index = lower_bound(리스트의 시작점, 리스트의 끝점, 찾을 key) - 리스트의 시작점

Reference & 다른 PS 모음집

---

https://github.com/ggh-png/PS

lower_bound

https://ggh-png.github.io/posts/cpp-stl-lowerBound/