백준 18870번 좌표 압축 JAVA 구현해보기

---

```

백준 18870번 좌표 압축 JAVA 구현해보기

```

이번 글을 통해 배워갈 내용

1. 백준 18870번 풀이

---

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

18870번: 좌표 압축

 

백준 18870번 좌표 압축은

난이도 실버 등급의 문제로서

 

수직선 위에 N개의 좌표 x1, x2, x3, x4 가 있다면

xi를 압축한 x'i는 xi> xj를 만족하는 서로 다른 좌표의 수와 같아야 합니다.

각 좌표에 x'를 구해주고

입력받은 순서대로 출력해주면 됩니다.

 

 

예

5
1 2 3 4 5
0 1 2 3 4

 

---

30분 정도 위에 링크를 방문하셔서 풀어보시고

안 풀리시는 경우에만 아래 해답을 봐주시면 감사하겠습니다.

---

 

각 좌표의 랭크를 구해주면 되는 문제입니다.

좌표 리스트 사이즈를 입력받고

좌표 리스트를 입력받은 다음

좌표 리스트를 가공해서 정렬된고유좌표 리스트를 구합니다.

 

좌표 리스트 사이즈만큼 좌표리스트를 돌면서

정렬된 고유 좌표 리스트에 lower bound 즉 행렬에서 많이 쓰는 랭크를 구해주고 출력해줍니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main {

    public static void main(String[] args) throws IOException {
        final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        final String input01 = br.readLine();
        final String input02 = br.readLine();
        System.out.print(solution(input01, input02));
    }

    private static String solution(String input01, String input02) {
        final int coordinateListSize = Integer.parseInt(input01);
        final List<Integer> coordinateList = Arrays.stream(input02.split(" "))
                .map(Integer::parseInt)
                .collect(Collectors.toList());
        final List<Integer> sortedDistinctCoordinateList = coordinateList.stream()
                .sorted()
                .distinct()
                .collect(Collectors.toList());

        StringBuilder sb = new StringBuilder();
        IntStream.range(0, coordinateListSize).forEach(idx ->
                sb.append(lowerBound(sortedDistinctCoordinateList, coordinateList.get(idx))).append(" ")
        );

        sb.setLength(sb.length() - 1);
        return sb.toString();
    }

    private static int lowerBound(List<Integer> sortedList, int target) {
        int begin = 0;
        int end = sortedList.size();

        while (begin < end) {
            int mid = (begin + end) / 2;

            if (sortedList.get(mid) >= target) {
                end = mid;
            } else {
                begin = mid + 1;
            }
        }
        return end;
    }
}

 

읽어주셔서 감사합니다

 

무엇인가 얻어가셨기를 바라며

 

오늘도 즐거운 코딩 하시길 바랍니다 ~ :)

 

---