백준18870문제
백준 18870번 문제를 풀면서 배운 것을 정리하자.

1.개요

수직선상의 좌표를 압축하는 문제다.
가장 작은 값 = 0, 그다음 작은 값 = 1 ...
이런 식으로 단순화 시키는 것.
(제한사항)

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

2. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
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[] X = new int[N];
        int[] sorted = new int[N];    // 정렬용 배열
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i =0; i<N;i++){
            X[i] = Integer.parseInt(st.nextToken());
            sorted[i] = X[i];
        }
        //sorted 배열 정렬
        Arrays.sort(sorted);
        //좌표와 등수를 저장할 맵
        Map<Integer, Integer> rankingMap = new HashMap<>();
        //배열 순서대로 등수 매기기
        int rank = 0;
        for(int v : sorted) {
            if(!rankingMap.containsKey(v)) {
                rankingMap.put(v, rank);
                rank++;
            }
        }        
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<X.length; i++){
                sb.append(rankingMap.get(X[i])).append(' ');
        }
        System.out.print(sb.toString());
    }
}

Map

Key를 통해 Value를 얻는 자료형(파이썬의 딕셔너리와 비슷하다)
Key는 중복을 허용하지 않는다.
Value는 중복을 허용한다.

Map<Integer, Integer> rankingMap = new HashMap<>();

rankingMap.put("key값", "Value값"); //Map 쓰기
rankingMap.get("key값"); //Value값 읽기

사용한 이유?
처음에는 2차원 배열로 코드를 구성하였는데 매긴 등수를 기존 N배열에 입력하는 과정에서 N배열과 2차원배열을 모두 순회해야해서 최악의 경우
시간 복잡도 : O(n2) 으로 시간초과 실패하였다.

HaskMap은 저장순서를 보장하지 않고 Hasing을 사용해서 시간을 줄일 수 있다.