[백준] 18770번: 좌표 압축 - Java

문제

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

주어진 좌표들을 압축하여 상대적인 순위를 매기는 문제,

주어진 좌표들이 [-10, -5, 2, 3, -10, -5]라면,

각 좌표의 상대적인 순위를 계산하여 [0, 1, 2, 3, 0, 1]로 변환하는 것으로

데이터의 양이 많아질 때도 효율적으로 처리할 수 있도록 하는 것이 중요하다.

 

접근 방법

• 원본 좌표를 배열에 저장: 입력된 좌표들을 그대로 배열에 저장합니다.
• 좌표 정렬: 원본 배열의 복사본을 만들어 이를 정렬합니다.
• 좌표 압축: 정렬된 배열을 순회하며, 각 좌표의 순위를 매겨 HashMap에 저장합니다.
• 결과 출력: 원본 배열을 순회하면서, HashMap에서 해당 좌표의 압축된 값을 가져와 출력합니다.

 

코드

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));
        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.clone(); // 기존 배열의 값을 복사해서 넣음
        Arrays.sort(sortArr); // 정렬

        Map<Integer, Integer> map = new HashMap<Integer, Integer>(); // 값과 요소의 순서(출력해야하는 값)을 쌍으로 저장

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

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

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

 

메모리:265104kb 시간:1796ms