[백준] 18870번 : 좌표 압축 - 자바(JAVA)

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

18870번: 좌표 압축

 

문제 해석

수직선 위에 N개의 좌표가 존재합니다.

이 좌표들을 압축하려고 합니다.

X(i)를 좌표 압축한 결과 X`(i)의 값은 X(i) > X(j)를 만족하는 서로 다른 좌표의 개수와 같아야 합니다.

 

문제만 보고 이해가 잘 되지 않으면 예제를 보면 이해하기 쉽습니다.

5
2 4 -10 4 -9

-10은 정렬했을 때 0번째 수, -9는 첫번째 수, 2는 두번째 수, 4는 세번째 수 입니다.

 

따라서 결과는 다음과 같습니다.

2 3 0 3 1

 

 

문제 풀이 전 설계

set을 활용하여 중복을 제거하여 랭킹을 부여합니다.

랭킹은 Map으로 관리합니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.stream.Collectors;

public class Main_18870_좌표압축 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        List<Long> originNumbers = new ArrayList<>();
        Set<Long> originNumbersSet = new HashSet<>();

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            Long curItem = Long.parseLong(st.nextToken());
            originNumbers.add(curItem);
            originNumbersSet.add(curItem);
        }

        List<Long> sortedList = originNumbersSet.stream()
                                             .sorted()
                                             .collect(Collectors.toList());


        Map<Long, Integer> rank = new HashMap<>();

        int size = sortedList.size();
        for (int i = 0; i < size; i++) {
            rank.put(sortedList.get(i), i);
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            Integer curRank = rank.get(originNumbers.get(i));
            sb.append(curRank + " ");
        }

        System.out.println(sb.toString()
                             .trim());

    }
}