[백준] 18870 : 좌표압축 (Hashmap과 Map) - JAVA

백준 단계별 문제풀이 13단계 (정렬)

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

18870번: 좌표 압축

 

 

# 문제

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

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

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

 

# 예제

입력 : 

• 1 ≤ N ≤ 1,000,000
• -109 ≤ Xi ≤ 109

5
2 4 -10 4 -9

 

출력

2 3 0 3 1

 

# 필요개념

 

문제를 읽고 들었던 생각은 "sort한 배열의 인덱스" 를 출력하면 되겠네! 였다. 오름차순 정렬을 하면 가장 작은 수의 인덱스는 0이 될 것이다. 이는 우리가 풀어야 하는 문제 즉,  Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같다. 우리가 신경써야 할 부분은 중복을 제거하는 것이다. 

 

처음엔 간단하게 stream의 sort와 distinct 메소드를 활용하려 했으나, 입력값의 크기가 만만치 않아 시간초과가 걸렸다. 그래서 생각한 방법은 int 배열 2개를 받아서 값이 같은 걸 찾아서 그의 인덱스를 출력해보자! 였다. 이렇게 풀면 배열 2개로는 쉽지 않아서 HashMap을 사용해보기로 했다.

 

Map

Map은 자바의 인터페이스로  key와 value를 한 쌍으로 갖는 자료구조이다. 이때  key값은 중복을 허락하지 않는다. 순서는 유지되지 않아 저장소 용도로 쓰인다. 인터페이스인 Map을 구현한 클래스 중 하나가 HashMap이다. HashMap 말고도 TreeMap, HashTableMap이 있다.

 

- HashMap은 Map을 구현한 클래스라고 보면 되고 key나 value값으로 null을 허용한다는 특징이 있다.

- TreeMap은 HashMap과 마찬가지로 key의 중복을 허용하지 않으나, 차이점은 SortedMap을 상속하여 key 값에 정렬이 이루어진다는 것이다.

- HashTableMap은 null을 허용하지 않는다.

 

잘 기억해뒀다가 상황에 따라 다르게 사용하면 될 것이다. 

 

# Code

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());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] sort = new int[n];
        int[] arr = new int[n];
        for (int i = 0 ; i < n ; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            sort[i] = arr[i];
        }
        HashMap<Integer,Integer> rank = new HashMap<Integer, Integer>();
        Arrays.sort(sort);

        int r = 0;
        for (int i : sort) {
            if (!rank.containsKey(i)) {
                rank.put(i, r);
                r++;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int j : arr) {
            int ranking = rank.get(j);
            sb.append(ranking).append(" ");
        }
        System.out.println(sb);
    }
}

 

하나하나 System.out.print를 쓰면 시간을 너무 많이 낭비하게 되기 때문에 StringBuilder를 사용하는 것이 좋다.

 

# 결과