백준 18870 좌표 압축[JAVA]

문제 해석

• 이 문제를 처음 마주했을 때 이게 무슨 소리이지 싶었다.
• 예시를 보고 문제를 이해했는데, 예시를 보면 입력이 2 4 -10 4 -9일때, 출력은 2 3 0 3 1이다.
• 이 예시를 통해 같은 값의 좌표가 있어도 그 값은 1개로 취급하는 것을 알 수 있다. (같은 값 4가 똑같이 3으로 출력되니까)

좌표

import java.io.*;
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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine()); //좌표의 개수

        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] notSortArr = new int[N]; //정렬하기 전에 저장할 배열
        for(int i = 0; i < N; i++){
            notSortArr[i] = Integer.parseInt(st.nextToken());
        }

        br.close();

        /*int[] sortArr = notSortArr; 하면 같은 주소(힙)값을 참조하므로 정렬을 시도하면 해당 값이 바뀌어버림*/
        int[] sortArr = notSortArr.clone(); //기존 배열의 값을 복사해서 넣음

        Arrays.sort(sortArr); // 정렬

        //중복값인 경우는 같은 값을 가지므로 HashMap으로 중복값을 체크해준다.
        Map<Integer, Integer> map = new HashMap<Integer, Integer>(); // 값과 요소의 순서(출력해야하는 값)을 쌍으로 저장

        int index = 0;
        // 비교할 배열 만들기
        for(int i : sortArr){ //sortArr정렬된 배열 반복문을 돎
            if(!map.containsKey(i)){ // map에 중복된 키가 없을 경우
                //해당 정렬된 값이 key가 된다.
                map.put(i, index++); //해당 값과 해당 요소의 순서를 map에 쌍으로 저장
            }
        }

        for(int i : notSortArr){ // 실질적인 출력값을 버퍼에 저장하기
            bw.write(map.get(i) + " "); //키로 값(앞축된 좌표, map 에 저장된 index를 넣어준다)
        }

        bw.flush();
        bw.close();


    }
}

• 코드에 대한 설명은 주석으로 작성해 두었다.
• 여기서 핵심인건 clone()인 것 같은데, 배열의 참조 형태를 기억해야한다!
• 또 핵심인것은 HashMap()이다. <키, 값>형태로 넣는데, 값이 정렬된 배열의 요소값이 아니고, 키가 배열의 요소 값이 된다!
• 그리고 그 배열의 요소로 HashMap()에 주었던 값(index)를 찾는다.

결과

느낀점

• 점점 풀수록 시간이랑 메모리를 줄이는 방법을 이해하기가 어려워지고 있다...
• 공부하는 방향성이 틀린 것인지... 어찌 해야할지 모르겠다😢