[JAVA] 백준 18870번 : 좌표 압축

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

18870번: 좌표 압축

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.stream.Collectors;

public class Main {
    static Map<Integer, Integer> map = new HashMap<>();
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        List<Integer> sorted = new ArrayList<>();
        for (int n : input) {
            sorted.add(n);
        }
        Collections.sort(sorted);

        map.put(sorted.get(0), 0);
        int cnt = 1;
        for (int i = 1; i < sorted.size(); i++) {
            if (!map.containsKey(sorted.get(i))) {
                map.put(sorted.get(i), cnt);
                cnt++;
            }
        }
        for (int n : input) {
            sb.append(map.get(n)).append(" ");
        }
        System.out.print(sb);
    }
}

💡 정렬

풀이 

❗ 틀린 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static Map<Integer, Integer> map = new HashMap<>();
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        List<Integer> sorted = new ArrayList<>();
        for (int n : input) {
            if(!sorted.contains(n))
                sorted.add(n);
        }
        Collections.sort(sorted);
        map.put(sorted.get(0), 0);
        int previous = sorted.get(0);
        for (int i = 1; i < sorted.size(); i++) {
            if (sorted.get(i) != previous) {
                map.put(sorted.get(i), i);
                previous = sorted.get(i);
            }
        }
        for (int n : input) {
            sb.append(map.get(n)).append(" ");
        }
        System.out.print(sb);
    }
}

• 좌표 압축 = 해당 좌표보다 값이 작은 좌표들의 개수
• 좌표 값 중복 가능함 →  동일한 좌표 값이 주어진 경우 동일한 압축 값으로 나와야 함
  • 입력값이 중복될 수 있음 →  중복 제거 해야 함

→  위 풀이는 시간 초과 

.. 카운팅 소트 사용 →  메모리 초과..ㅠ

---

최종

1. 좌표 입력 값을 받아온 후, 배열에 복사해 오름차순 정렬함

2. 정렬된 배열에서 새로운 수가 나올 때 마다 최근 순위에 +1한 것을 값으로 좌표 압축 실행

   - Map.containsKey()로 중복 제거

3. map 돌면서 좌표에 대응되는 압축 값 추가

💡 시간 제한 2초, 입력 크기가 10^6 이므로 시간 복잡도를 O(NlogN)으로 맞춰줘야 함 (O(n^2) 금지!)
   Collections.contains(e)는 시간 복잡도 O(n) 이므로 시간 복잡도가 O(N*N)이 됨
   ➡️ Map.containsKey(), get() 는 시간복잡도 O(1) 이므로 map을 사용해 시간 복잡도를 줄이자
➕ Collections.sort()의 시간복잡도는 O(NlogN) (평균/최악) 이므로 최종 시간 복잡도는 O(NlogN)이 됨
➕ Arrays.sort()의 시간복잡도는 O(N^2) (최악)이므로 차순위로...