[Lv.1] 좌표 압축

문제 이해

주어진 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있습니다. 이 좌표에 좌표 압축을 적용하려고 합니다. 좌표 압축을 적용한 결과 X'i의 값은 Xi보다 큰 다른 좌표의 개수와 같아야 합니다. 주어진 좌표를 압축한 결과를 출력해야 합니다.

알고리즘 설계

1. 먼저, 입력으로 주어진 좌표들을 배열에 저장합니다.
2. 중복을 제거하고 정렬한 새로운 리스트를 만듭니다.
3. 각 좌표의 압축된 값을 저장할 맵을 생성합니다.
4. 좌표를 순회하면서 압축된 값을 출력합니다.

소스 코드 구현

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int N = scanner.nextInt(); // 좌표의 개수 입력
        int[] X = new int[N]; // 좌표를 저장할 배열
        
        // 좌표들을 배열에 저장
        for (int i = 0; i < N; i++) {
            X[i] = scanner.nextInt();
        }
        
        // 중복을 제거하고 정렬한 새로운 리스트를 만듦
        Set<Integer> sortedXSet = new TreeSet<>();
        for (int i = 0; i < N; i++) {
            sortedXSet.add(X[i]);
        }
        
        List<Integer> sortedXList = new ArrayList<>(sortedXSet);
        
        // 각 좌표의 압축된 값을 저장할 맵 생성
        Map<Integer, Integer> compressedXMap = new HashMap<>();
        for (int i = 0; i < sortedXList.size(); i++) {
            compressedXMap.put(sortedXList.get(i), i);
        }
        
        // 좌표를 순회하면서 압축된 값을 출력
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < N; i++) {
            result.append(compressedXMap.get(X[i])).append(" ");
        }
        
        System.out.println(result.toString());
    }
}

소스 코드 분석

이 코드는 주어진 수직선 상의 좌표들을 압축하는 기능을 수행합니다.

1. 입력 받기 및 좌표 저장:

   프로그램은 먼저 좌표의 개수(N)를 입력받습니다. 그 후에 N개의 좌표를 입력받아 배열에 저장합니다.

2. 좌표 압축:

   중복을 제거하고 정렬한 새로운 리스트를 만들기 위해 TreeSet을 사용합니다. 이 리스트에는 중복을 제거하고 정렬된 좌표가 저장됩니다. 그 다음 리스트를 순회하면서 각 좌표에 대해 압축된 값을 저장하기 위해 HashMap을 사용합니다. 이를 통해 각 좌표의 압축된 값을 맵에 저장합니다.

3. 압축된 좌표 출력:

   원래의 좌표 배열을 순회하면서 각 좌표의 압축된 값을 출력합니다. 이를 통해 좌표 압축된 결과를 출력합니다.

코드의 시간 복잡도는 좌표의 개수(N)에 비례합니다. TreeSet과 HashMap의 삽입 및 조회 작업은 대부분 O(logN) 또는 O(1)에 수행되므로 전체적으로 O(NlogN) 또는 O(N)의 시간 복잡도를 가집니다.