BOJ - 18870 - 좌표압축

ggh·2022년 5월 11일

Sort boj cpp ps

백준

목록 보기

8/112

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) - 리스트의 시작점