[백준] 18770번 : 좌표 압축

 

1. 문제 설명

 

2. 풀이 방법

중복을 제외하고 자기보다 작은 값들을 구하면 되는 것이므로, 기본의 배열은 그대로 두고

중복을 제거한 새로운 리스트를 통해 해당 인덱스를 구하기로 함

 

[초반 풀이]

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

import java.io.*; import java.util.*;   public class Main {       public static void main(String[] args) throws IOException {           BufferedReader br=new BufferedReader(new InputStreamReader(System.in));           int n=Integer.parseInt(br.readLine());         int arr[]=new int[n];         Set<Integer> set=new HashSet<>();         StringTokenizer st=new StringTokenizer(br.readLine());         for(int i=0;i<n;i++){             arr[i]=Integer.parseInt(st.nextToken());             set.add(arr[i]);         }           ArrayList<Integer> list=new ArrayList<>();         for(int num:set){             list.add(num);         }         Collections.sort(list);         StringBuilder sb=new StringBuilder();           for(int i=0;i<n;i++){             int idx = list.indexOf(arr[i]);             sb.append(idx+" ");         }         System.out.println(sb.toString());     } }

결과 : 시간초과

원인 : indexOf()의 시간복잡도가 O(n)이고, 총 O(n2)으로 N의 범위가 1<=N<=1,000,000 이기에 불가능

 

 

 

[최종 풀이]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

import java.io.*; import java.util.*;   public class Main {       public static void main(String[] args) throws IOException {           BufferedReader br=new BufferedReader(new InputStreamReader(System.in));           int n=Integer.parseInt(br.readLine());         int arr[]=new int[n];         Set<Integer> set=new HashSet<>();         StringTokenizer st=new StringTokenizer(br.readLine());         for(int i=0;i<n;i++){             arr[i]=Integer.parseInt(st.nextToken());             set.add(arr[i]);         }           ArrayList<Integer> list=new ArrayList<>();         for(int num:set){             list.add(num);         }         Collections.sort(list);           HashMap<Integer,Integer> map=new HashMap<>();         int idx=0;         for(int i=0;i<list.size();i++){             map.put(list.get(i),idx++);         }         StringBuilder sb=new StringBuilder();         for(int i:arr){             sb.append(map.get(i)).append(" ");         }         System.out.println(sb.toString());       } }

결국 핵심은, 나보다 작은 것들의 값을 count 하는 작업이 필요하므로,

HashMap을 통해 인덱스를 순차적 입력 후, 배열과 비교하여 출력