[좌표압축] 백준 18870번 좌표압축 c++, java 풀이

BOJ 18870번 좌표 압축 c++ 풀이

• 난이도: 실버2
• 백준 18870번 좌표 압축
  
  
  

문제 정리

1. 수직선 위의 값이 주어질때 이를 좌표압축해여 표현하여라
2. 주어지는 수의 개수는 1 <= N <= 1,000,000
3. 주어지는 수는 -10^9 <= X <= 10^9
   
   
   

문제 접근

좌표 압축 문제를 처음 풀어보아서 개념을 익히고 다른 분의 코드를 참고하여 디버깅을 통해 이해하였습니다.
중복된 수를 제거하고 정렬한 상태에서 lower_bound를 통해 나온 위치 값이 압축한 값이 됩니다.
c++은 vector를 이용하여 중복된 값을 제거하고 lower_bound를 이용하여 좌표 압축을 진행합니다.
java는 arraylist를 이용하여 같은 방식으로 제거합니다. lower_bound는 직접 구현합니다

좌표 압축

좌표 압축은 주어지는 수의 범위가 매우 크지만 그 범위의 수 중에서
나오는 수는 그렇게 많지 않을때 사용합니다.
만약 범위가 -10억 ~ 10억 인데 숫자는 10만개 밖에 없다면 좌표 압축을 통해 범위를 줄여서 무언가를 수행한다면 더욱 효율적으로 할 수 있습니다.
이는 세그먼트 트리나 구간 쿼리 처리에 쓰이는 경우가 많다고 합니다.

c++ 문제 풀이

1. vector를 이용하여 좌표 값을 모두 입력 받습니다. 이때 원래 상태를 저장하기 위해 두 개의 벡터에 입력받습니다.
2. 중복된 수를 제거하기 위해 오름차순으로 정렬합니다.
3. 그리고 unique를 이용하여 중복된 수를 뒤로 밀고 resize나 erase를 이용해서 뒤로 밀려난 중복된 수를 제거합니다.
4. 그리고 lower_bound를 이용하여 원래의 수를 찾습니다. 즉 index의 위치가 좌표 압축을 한 값이 됩니다.
   
   
   

자바 문제 풀이

기본적으로 c++의 풀이한 개념을 그대로 사용하였습니다.
처음에는 list.remove를 이용하여 지워나갔지만 내부적으로 시간이 많이 걸려서 그렇지 시간초과가 발생하여 새로운 list를 만들어 해결하였습니다.

1. 원래의 수 순서대로 담은 리스트와 정렬할 리스트 두개를 생성한다.
2. 중복된 수를 제거하기 위해 정렬을 합니다.
3. 정렬된 수를 탐색하며 이전 수와 같지 않은 경우에만 새로운 list에 넣습니다. -> 중복 제거
4. 이렇게 하면 마지막 원소가 들어가지 않기 때문에 마지막 원소를 따로 넣어줍니다.
5. lower_bound를 이용하여 원소의 인덱스를 찾아서 좌표 압축을 진행합니다.
6. 위치를 모두 StringBuilder에 담았다가 한번에 출력합니다.(최대 10만개로 출력 개수가 많기 때문)
   
   
   

c++ erase 인자 1개

v.erase(iter)
iter가 가리키는 원소 제거
size만 줄어들고 capacity(할당된 메모리)는 그대로 남는다
erase는 파라미터 하나를 받을때와 두개를 받을 때 다르다

c++ erase 인자 두개

v.erase(start, end)
start, end 범위의 인자를 삭제 (start 이상 end 미만의 인자)

c++ unique

unique
연속된 중복 원소를 vector의 제일 뒷부분으로 쓰레기값으로 보내버린다.
-> 반환되는 값이 쓰레기값의 첫번째 위치가 된다.
이에 end까지 erase하면 중복된 원소 제거가능

백준 18870 좌표압축 java 코드

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.ArrayList;
	import java.util.Collections;
	class Main {
	static int N;
	static ArrayList<Integer> arr, arr2, idx;
	public static void main(String[] args) throws IOException{
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringBuilder sb = new StringBuilder();
	N = Integer.parseInt(br.readLine());
	String[] temp = br.readLine().split(" ");
	arr = new ArrayList<>();
	arr2 = new ArrayList<>();
	idx = new ArrayList<>();
	for(int i=0; i<N; i++){
	int a = Integer.parseInt(temp[i]);
	arr.add(a);
	idx.add(a);
	}
	// 중복된 수 제거
	Collections.sort(idx);
	for(int i=0; i<idx.size()-1; i++){
	if(!idx.get(i).equals(idx.get(i+1)))
	arr2.add(idx.get(i));
	}
	arr2.add(idx.get(idx.size()-1)); // 마지막 원소 넣기
	for(int a : arr){
	int pos = lower_bound(a);
	sb.append(pos + " ");
	}
	System.out.println(sb);
	br.close();
	}
	public static int lower_bound(int target){
	int left = 0;
	int right = arr2.size() - 1;
	while(left < right){
	int mid = (left + right ) / 2;
	if(arr2.get(mid) >= target)
	right = mid;
	else
	left = mid + 1;
	}
	return right;
	}
	}

view raw BOJ18870.java hosted with ❤ by GitHub

백준 18870 좌표압축 c++ 코드

	#include <iostream>
	#include <algorithm> // sort와 unique 사용
	#include <vector>
	using namespace std;
	int N;
	vector<int> v, idx;
	int main() {
	// IO 속도 향상
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N;
	for (int i = 0; i < N; i++) {
	int a;
	cin >> a;
	v.push_back(a); // push_back: 마지막 원소 뒤에 삽입
	idx.push_back(a);
	}
	sort(idx.begin(), idx.end()); // 정렬
	idx.resize(unique(idx.begin(), idx.end()) - idx.begin());
	//idx.erase(unique(idx.begin(), idx.end()), idx.end()); // 중복 제거
	for (int a : v) {
	int pos = lower_bound(idx.begin(), idx.end(), a) - idx.begin();
	cout << pos << ' ';
	}
	return 0;
	}

view raw BOJ18870.cpp hosted with ❤ by GitHub

 

풀이 인증