[정렬] 백준 18870번 좌표 압축 java(자바)

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

18870번: 좌표 압축

문제

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 (배열)

시간초과남

import java.util.*;

public class No18870 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] arr1 = new int[N];
        int[] arr2= new int[N]; //압축한 숫자
        for(int i=0; i<N; i++){
            arr1[i] = sc.nextInt();
                arr2[i] = arr1[i];

        }
        Arrays.sort(arr2); //정렬
       arr2 = Arrays.stream(arr2).distinct().toArray();

        for(int i=0; i<N; i++){
            for(int j=0; j<arr2.length; j++){
                if(arr1[i] == arr2[j]){
                    arr1[i] = j;
                }
            }
        }
        for(int i=0; i<N; i++){
            System.out.print(arr1[i]+" ");
        }

    }
}

코드2 (Map 사용)

시간초과남

import java.util.*;

public class No18870 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] arr1 = new int[N]; //원본 배열
        int[] arr2= new int[N]; //정렬한 배열
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i=0; i<N; i++){
            arr2[i] = arr1[i] = sc.nextInt();
        }
        Arrays.sort(arr2); //정렬

        int i = 0;
        for(int a : arr2){
            if(!map.containsKey(a)) {   //중복 제거하면서 map에 삽입
                map.put(a, i);
                i++;
            }
        }

        for(int j = 0; j< arr1.length;j++){
            arr1[j] = map.get(arr1[j]);
        }
        for(int j=0; j<N; j++){
            System.out.print(arr1[j]+" ");
        }

    }
}

코드3(Map & StringBulider)

시간초과가 계속 나서 구글링 해봤더니 StringBulider를 사용하는 코드가 있어서 따라해보니 시간초과 문제를 해결했다.

import java.util.*;

public class No18870 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] arr1 = new int[N]; //원본 배열
        int[] arr2= new int[N]; //정렬한 배열
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i=0; i<N; i++){
            arr2[i] = arr1[i] = sc.nextInt();
        }
        Arrays.sort(arr2); //정렬

        int i = 0;
        for(int a : arr2){
            if(!map.containsKey(a)) {   //중복 제거하면서 map에 삽입
                map.put(a, i);
                i++;
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int key : arr1) {
            int ranking = map.get(key);
            sb.append(ranking).append(' ');
        }

        System.out.println(sb);

    }
}

 

풀이

1. 아래와 같은 좌표가 입력되었다고 되었다고 하면,

해당 배열을 아래와 같이 정렬한다.

3. 중복을 제거하고, 각 숫자에 순서대로 값을 메긴다.

4. 1번에 있는 그림에 3번에 각 숫자에 메겼던 값을 대입하면 정답이 나온다.

주의 사항

해당 문제의 시간제한이 너무 짧아서 답이 출력 되더라도 시간제한으로 오답이 될 수 있으니 시간 복잡도를 잘 고려해야 한다.