[BOJ] 18870. 좌표 압축

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

18870번: 좌표 압축

---

접근 방법

HashMap을 이용해서 풀었다. 단순 반복문으로는 시간이 초과되는 반면 HashMap으로는 통과하였다.

이 문제를 풀기 위한 필수 정보는 기존 인덱스, 값, 계산 후 값이다.

인덱스를 Key 로 부여하면 Value 기준 정렬 후 계산하고 원래 인덱스 순서로 복구하기가 쉬울 듯해서 택했다.

허나 이것이 실전이었다면 정렬 부분에서부터 헤매었을 것이다.

좀 더 단순한 방법을 생각해 보다가 2차원 배열이 떠올랐다.

배열 정렬 시 각 부분 배열의 n번째 요소를 기준으로 정렬이 된다고 한다. 메모리나 시간도 더 단축됐다.

 

소스 코드

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Map<Integer, Integer> m = new HashMap<>();
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i=0; i<N; i++)
            m.put(i, Integer.valueOf(st.nextToken()));
        
        List<Integer> a = new ArrayList<>(a.keySet());
        a.sort((o1, o2) -> m.get(o2).compareTo(m.get(o1)));
        
        int cnt = 0;
        int min = m.get(a.get(N-1));
        
        for(int i=N-1; i>=0; i--) {
            if(min < m.get(a.get(i))) {
                min = m.get(a.get(i));
                cnt += 1;
            }
            m.put(a.get(i), cnt);
        }
        
        StringBuilder bd = new StringBuilder();
        for(int i=0; i<N; i++)
            bd.append(m.get(i) + " ");
        System.out.println(bd.toString());
    }
}

HashMap 이용 버전

import java.util.*;
import java.io.*;

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[][] n = new int[N][3];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i=0; i<N; i++) {
            int num = Integer.valueOf(st.nextToken());
            n[i][0] = num;
            n[i][1] = i;
        }
        Arrays.sort(n, Comparator.comparingInt(o1 -> o1[0]));
        
        int cnt = 0;
        int min = n[0][0];
        
        for(int i=0; i<N; i++) {
            if(min < n[i][0]) {
                min = n[i][0];
                cnt += 1;
            }
            n[i][2] = cnt;
        }
        Arrays.sort(n, Comparator.comparingInt(o1 -> o1[1]));

        StringBuilder bd = new StringBuilder();
        for(int i=0; i<N; i++)
            bd.append(n[i][2] + " ");
        System.out.println(bd.toString());
    }
}

2차원 배열 이용 버전