[240225] 알고리즘 리부트 16일차 - 백준 18870 자바

[Part1-Chapter05-Clip06]

- 백준 18870 좌표 압축

 

 

 

로직이 머리 속에서 한참 꼬여서 애를 먹었다. 처음에는 카운팅 배열을 쓰고자 했다. 간단하게 풀이가 가능할 것 같았지만 메모리 초과로 사용할 수 없었다. 어쩔 수 없이 다른 자료구조를 고민했다. 이차원 배열을 쓰자니 중복처리하는데 번거로울 것 같았고 해시셋을 쓰자니 순서부여가 어려워 해시맵을 이용해서 처리했다. 이미 키가 존재한다면 넘어가고 순서를 부여하는 인덱스를 별도로 관리했다. 

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[] arr = new int[n];
        int[] temp = new int[n];

        for (int i = 0; i < n; i++) {
            int thisNum = sc.nextInt();
            arr[i] = thisNum;
            temp[i] = thisNum;
        }

        // 임시배열은 정렬해주기
        Arrays.sort(temp);

        HashMap<Integer, Integer> map = new HashMap<>();

        int idx = 0;
        for (int i = 0; i < n; i++) {
            if (map.containsKey(temp[i]))
                continue;

            map.put(temp[i], idx);
            idx++;
        }

        for (int i = 0; i < n; i++) {
            arr[i] = map.get(arr[i]);
        }

        StringBuilder sb = new StringBuilder();

        for (int i : arr) {
            sb.append(i + " ");
        }

        System.out.println(sb);


    }
}