[JAVA] 백준 18870 좌표 압축

Java/백준

[JAVA] 백준 18870 좌표 압축

쥬크버그 2024. 2. 7. 18:12

18870번: 좌표 압축

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

www.acmicpc.net

풀이 과정

- original 배열을 sorted배열로 clone

- sorted 배열을 arrays.sort로 오름차순 정렬

- sorted 배열을 value로 추가

- original 배열을 key로 하고 sorted 배열을 value로 하는 HashMap을 이용

참고 블로그

[백준] 18870번 : 좌표 압축 - JAVA [자바] (tistory.com)

[백준] 18870번 : 좌표 압축 - JAVA [자바]

https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다

st-lab.tistory.com

정답

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.HashMap;


public class Main {
    public static void main(String[] args) throws IOException, NumberFormatException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int num = Integer.parseInt(br.readLine());
        int original[] = new int[num];
        int sorted[] = new int[num];
        
        HashMap<Integer, Integer> map = new HashMap<>();
        
        String[] input = br.readLine().split(" ");
        for(int i=0; i<num; i++)
        {
        	original[i] = Integer.parseInt(input[i]);
        }
        
        sorted = original.clone();
        
        Arrays.sort(sorted);
        
        int count=0; 
        for(int i=0; i<num; i++)
        {
        	int key=sorted[i];
        	
        	if(!map.containsKey(key))
        	{
        		map.put(key, count++);
        	}
        }
        
        for(int i=0; i<num; i++)
        {
        	int key = original[i];
        	
            bw.write(map.get(key)+" ");
        }
        
        bw.flush();
        bw.close();
        
    }
}