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

안녕하세요. 이번에는 백준 18870 좌표 압축 문제를 풀어보려고 합니다.

https://www.acmicpc.net/problem/18870

18870번: 좌표 압축

---

Problem

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

사진 1. 문제

---

Solution

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());    
        }
        
        int[] copy = arr.clone();
        
        Arrays.sort(copy);
       
        HashMap<Integer, Integer> map = new HashMap<>();
        int count = 0;
        
        for(int i = 0; i < N; i++) {
            int key = copy[i];
            
            if(!map.containsKey(key)) {
                map.put(key, count++);    
            }
        }
        
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < N; i++) {
            int key = arr[i];
            
            sb.append(map.get(key)).append(" ");
        }
        
        System.out.println(sb.toString());
    }
}

 

 이번 문제는 HashMap을 사용하여 키 - 값을 활용하여 문제를 풀어보았다. arr 배열을 copy 배열로 clone 한 후 오름차순 정렬을 해준다. 그다음 오름차순 정렬들을 hashMap에 키 value로 추가시킨다. 이때 containsKey 기능을 통해서 키 값이 존재하는지 파악할 수 있다. 

 

1. 핵심 코드

	HashMap<Integer, Integer> map = new HashMap<>();
        int count = 0;
        
        for(int i = 0; i < N; i++) {
            int key = copy[i];
            if(!map.containsKey(key)) {
                map.put(key, count++);    
            }
            
        }

---

Performance

사진 2. 실행 결과