[백준] 18870

당당·2023년 4월 29일

18870 값 / 좌표 압축 백준 정렬

백준

목록 보기

70/179

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

📔문제

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

📝입력

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된X1, X2, ..., XN이 주어진다.

📺출력

첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

🚫제한

1 ≤ N ≤ 1,000,000
109 ≤ Xi ≤ 109

📝예제 입력 1

5
2 4 -10 4 -9

📺예제 출력 1

2 3 0 3 1

📝예제 입력 2

6
1000 999 1000 999 1000 999

📺예제 출력 2

1 0 1 0 1 0

🔍출처

-문제를 만든 사람: baekjoon

🧮알고리즘 분류

정렬
값 / 좌표 압축

📃소스 코드

import java.io.*;
import java.util.*;
import java.util.stream.Stream;

class Pair{
    int index;
    int value;

    public Pair(int index, int value){
        this.index=index;
        this.value=value;
    }
}

public class Code18870 {
    public static void main(String[] args) throws IOException {

        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int N=Integer.valueOf(br.readLine());

        String nums=br.readLine();
        int[] dot= Stream.of(nums.split(" ")).mapToInt(Integer::parseInt).toArray();
        br.close();
        int prior=0;
        int priorvalue=0;


        List numbers=new ArrayList();

        for(int i=0;i<N;i++){
            numbers.add(new Pair(i,dot[i]));
        }

        Collections.sort(numbers, new Comparator() {
            public int compare(Object o1,Object o2){
                return (((Pair)o1).value) - (((Pair)o2).value);
            }
        });

        int rank=0;
        int priorrank=0;
        for(Object pair: numbers){
            Integer temp=(((Pair)pair).value);//-10

            ((Pair) pair).value=rank;

            if(rank!=0 && prior==temp){ // -10 -9 2 4 4
//                rank=rank-1;
                ((Pair) pair).value=priorrank;
            }
            else{
                rank++;
            }

            priorrank=((Pair) pair).value;
            prior=temp;
        }

        Collections.sort(numbers, new Comparator() {
            public int compare(Object o1,Object o2){
                return (((Pair)o1).index) - (((Pair)o2).index);
            }
        });

        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        int plus=0;
        for(Object pair: numbers){
            String answer=String.valueOf(((Pair) pair).value);
            if(plus+1==N){
                bw.write(answer);
            }
            else{
                bw.write(answer+" ");
            }
            plus++;

        }

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

    }
}