백준 18870번: 좌표 압축

문제를 이해하는데 시간이 꽤 걸렸다. 문제를 설명하자면, 입력 받은 수가 해당 입력받은 수들의 배열에서 자신보다 적은 수는 몇개가 있는지를 구하는것이다. 이때, 중복은된 수는 제외한다. 즉 2,1,1,4 이렇게 입력을 받으면 2를 압축시키면 1이 된다. 자신보다 작은 수 1이 있기 때문이고, 중복은 제외하기 때문이다.

 

푸는 방법은 처음에는 카운팅 정렬로 풀으려고 했지만 카운팅은 딱히 의미가 없기에 중복되지 않는 수를 가지는 배열을 만들고, 오름차순으로 정렬을 한 후 입력받은 배열에 해당하는 값을 중복되지 않는 배열의 값이 같은 인덱스를 출력하는 식으로 풀었다.

 

다만 이 알고리즘은 풀리기는 하나 시간초과가 뜬다. 아무래도 수가 넓게 퍼져있으면 그만큼 시간이 오래걸려서 그런듯 하다.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        int[] arr=new int[n];
        List<Integer> di_list=new ArrayList();
        for(int i=0;i<n;i++){
            arr[i]= scanner.nextInt();
            if(i==0)
                di_list.add(arr[i]);
            else {
                for (int j = 0; j < di_list.size(); j++) {
                    if (di_list.get(j) == arr[i]) {
                        break;
                    } else if (j == di_list.size() - 1) {
                        di_list.add(arr[i]);
                        break;
                    }
                }
            }
        }

        scanner.nextLine();
        Collections.sort(di_list);

        for(int i=0;i<arr.length;i++){
           System.out.print(di_list.indexOf(arr[i])+" ");
        }
    }
}