[백준-자바] N_18870 좌표 압축

0woy·2024년 11월 7일

Map 백준 자바 정렬

코딩테스트

목록 보기

37/42

📜 문제

문제 이름에 어그로 끌려서 압축을 어떻게 했길래 입출력이 이모양이지 생각했지만, 모든 원소 중 현재 원소보다 작은 친구들 개수 구하는 문제.

생각하기

난 인덱스 초과 에러 다음으로 시간 초과에 걸리면 기분이 나쁘기에
시간 제한과 N의 최댓값을 보고 시간 복잡도를 먼저 생각합니다. (최근에 들인 좋은 습관)

1초당 보통 1억 번의 연산이라고 생각하면 돼서, 2초니까 우린 2억 번 연산 내로 풀어야 해요.
O(N²)= 1조니까 중첩 반복문 돌리는 순간 시간 초과 엔딩남

그렇다면, O(NlogN)은 어떨까?
N=1,000,000일 때,Log(1,000,000) ≒ 20.
즉, 2천만번이라서 다행히 시간초과 안 납니다.

그런데 처음에 귀신 씌어서 Log(1,000,000)을 1,000으로 계산해가지고 O(NlogN)도 시간초과 나는줄 알고 좀 고민 많이 했다...

왜 고민했냐면, 배열을 정렬하는 Arrays.sort 함수가 O(NlogN) 걸려서 이거 쓰면 안 되는 줄 알았음..

그래놓고 우선순위 큐 썼는데, 알고보니 PQ 풀이도 같은 시간복잡도라서 멍청 시간만 썼다.

그래서 두 가지 풀이가 있다. 우선순위 큐, 그리고 배열 정렬
둘 다 설명할 건데, 배열 정렬이 더 효율적임

✍ 풀이 방법

1. Priority Queue & HashMap

   public static void main(String[] args) throws IOException {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int [] arr = new int[n];
        Map<Integer, Integer> map = new HashMap<>();
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int i=0;
        while(st.hasMoreTokens()){
            int val = Integer.parseInt(st.nextToken());
            pq.add(val);
            arr[i++]=val;
        }

        int count = 0;
        while(!pq.isEmpty()){
            int prev = pq.poll();
            map.put(prev, count);
            if(!pq.isEmpty() && prev!=pq.peek()){
                count++;
            }
        }
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int key: arr){
            bw.write(map.get(key)+" ");
        }
        bw.flush();
        bw.close();
    }

arr : 주어진 순서대로 숫자 저장
map : (key: 숫자, value: key보다 작은 원소 개수)
pq : 오름차순 정렬에 사용

입력 받은 원소들을 pq와 arr 배열에 삽입
pq는 나중에 뽑아낼 때 작은 친구들 부터 뽑아낼 거고, arr은 출력에 쓰려고 함.
map의 key는 pq에서 뽑아낸 값, value는 count 값 저장.
중복값이 존재할 수도 있으니, 현재 원소와 그 다음으로 작은 원소가 같으면 count를 증가시키지 않습니다.
입력 받은 순서대로 값을 출력해야 하니 arr 배열에 저장된 원소를 key값으로 map에서 value를 취해 출력

Q. arr배열 안 만들고 대신 순서 보장해 주는 LinkedHashMap 써서, map.values() 하면 안 됨?

A. ㅇㅇ 해봤는데 중복 원소 허용이라 안 됨
ex) 2, 4, -10, 4, -9 들어오면 1, 3, 0, 1 나와서 4가 씹힙니다.

암튼 이렇게 풀면 배열 두 개 놓고 정렬 원소 쓰는 것보다
메모리, 시간 면에서 비효율적입니다.

그냥 굳이 이렇게 풀 수도 있구나.. 라고 생각하면 됨

2. Arrays.sort & HashMap

 public static void main(String[] args) throws IOException {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        Map<Integer, Integer> map = new HashMap<>();
        int [] arr  =new int[n];
        int [] sorted  =new int[n];

        for(int i=0;i<n;i++){
            int v =  Integer.parseInt(st.nextToken());
            arr[i] =v;
            sorted[i] =v;
        }
        Arrays.sort(sorted);
        int count =0;
        for(int v: sorted){
            if(map.containsKey(v)){
                continue;
            }
            map.put(v, count++);
        }

        for(int v: arr){
            bw.write(map.get(v)+" ");
        }
        bw.flush();
        bw.close();
    }

arr, map : PQ 풀이와 역할 같음
sorted: 원소 정렬 후 배열