공부공간

BOJ - 18870 ) 좌표압축 본문

알고리즘/구현,시뮬

BOJ - 18870 ) 좌표압축

개발자가될수있을까? 2020. 11. 24. 10:45


www.acmicpc.net/problem/18870

 

18870번: 좌표 압축

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌

www.acmicpc.net


좌표 압축 (Coordinate Compress)은 말그래도 좌표를 압축하여 사용하는 것이다.

 

단독으로 이것만 나오지 않고 보통 세그먼트트리나 구현문제에서 좌표를 압축해도 문제상황이

 

달라지지 않는 경우에 사용한다.

 

배열을 정렬해주고 작은 값에 인덱스를0을 부여하며 증가시켜서 압축시키는 방식이다.

 

아래는 구현코드 hashmap을 이용하여 압축하였다. 배열을 써도될듯 이분탐색이나.. 


import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		int num[] = new int[n];
		for(int i=0;i<n;i++) {num[i] = Integer.parseInt(st.nextToken());}
		HashMap<Integer, Integer> hm = new HashMap<>();
		int index =0;
		int tnum[] = num.clone();
		Arrays.sort(num);
		int s = 2147000000;
		for(int i=0;i<n;i++) {
			if(s!=num[i]) {
				hm.put(num[i], index++);
				s=num[i];
			}
		}
		StringBuilder sb = new StringBuilder();
		for(int i=0;i<n;i++) {
			sb.append(hm.get(tnum[i])+" ");
		}System.out.println(sb);
	}

}

'알고리즘 > 구현,시뮬' 카테고리의 다른 글

BOJ - 2170 ) 선 긋기  (0) 2021.06.02
BOJ - 11003 ) 최솟값 찾기  (0) 2021.03.10
BOJ - 14719 ) 빗물  (0) 2020.10.26
BOJ - 17837 ) 새로운게임 2  (0) 2020.10.16
BOJ - 17140 ) 이차원 배열과 연산  (1) 2020.09.14
Comments