[백준 문제 풀이] 18870번 좌표 압축

Junu Kim·2025년 12월 29일

Java baekjoon boj

코딩테스트 문제 풀이 (백준, HackerRank)

목록 보기

75/89

[18870] 좌표 압축

난이도: ★★★☆☆ • solved on: 2025-12-29

문제 요약

문제 유형: 정렬, 해시(좌표 압축)
요구사항: 주어진 수열의 각 값에 대해, 중복 제거 후 정렬했을 때의 인덱스를 원래 순서대로 출력해야 한다.

사용 개념

자료구조
- HashSet : 중복 제거
- ArrayList : 유니크 값 정렬
- HashMap : 값 → 압축 인덱스 매핑
- int[] : 숫자 배열 처리
- StringTokenizer : 빠른 입력 파싱
알고리즘/기법
- 좌표 압축 (coordinate compression):
  - 중복 제거 → 정렬 → rank(0..k-1) 부여 → 원본 순서대로 출력
  - 원래 가지고 있던 값들의 의미는 모두 사라지고 오직 순서에 따른 정보만 남게 되는 테크닉
핵심 키워드
- value-to-rank mapping (값→순위 매핑)
- unique + sort + map

풀이 아이디어 및 코드

방법 1 : HashSet 중복 제거 + 정렬 + HashMap 매핑

문제 분해

입력 수열을 문자열 배열로 받고 HashSet으로 중복 제거한다.

유니크 값 리스트(arrList)를 정렬한다.

정렬된 유니크 리스트의 인덱스를 HashMap에 저장해 값→순위 매핑을 만든다.

원본 배열을 순회하면서 map.get(num)으로 순위를 출력한다.
핵심 로직 흐름
arr = 입력(문자열)
set = 중복 제거
arrList = set -> 리스트 변환
arrList 정렬

map[value] = 정렬 인덱스
for num in arr:
    출력 map[num]
예외 처리

중복이 많아도 HashSet으로 유니크만 정렬하므로 정렬 대상이 줄어든다.

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

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = Integer.parseInt(sc.nextLine());
        String line = sc.nextLine();
        String[] arr = line.split(" ");
        HashSet<String> set = new HashSet<>(Arrays.asList(arr));
        ArrayList<String> arrList = new ArrayList<>(set);

        arrList.sort((a,b)-> {
            return Integer.valueOf(a).compareTo(Integer.valueOf(b));
        });
        HashMap<String, Integer> map = new HashMap<>();
        for(int i = 0; i < arrList.size(); i++) {
            map.put(arrList.get(i), i);
        }
        StringBuilder sb = new StringBuilder();
        for(String num : arr){
            sb.append(map.get(num)).append(" ");
        }
        System.out.println(sb);
    }
}

방법 2 : int 배열 복사본 정렬 + 중복 스캔으로 rank 매핑 + 빠른 입력

핵심 개선 포인트

Scanner/split 대신 BufferedReader + StringTokenizer로 입력 비용을 줄인다.

String 대신 int로 처리해 변환/비교 비용을 줄인다.

HashSet 없이도, 정렬된 배열을 한 번 스캔하며 중복을 제거하면서 map을 만들 수 있다.
핵심 로직 흐름
origin = 원본 int[]
sorted = origin 복사본
sorted 정렬

rank = 0
for i in 0..n-1:
    if i==0 or sorted[i] != sorted[i-1]:
        map[sorted[i]] = rank++
for x in origin:
    출력 map[x]
예외 처리

음수/큰 수여도 정렬 후 인덱스 기반이므로 문제 없음

출력 마지막 공백은 조건으로 처리

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[] origin = new int[n];
        int[] sorted = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            int v = Integer.parseInt(st.nextToken());
            origin[i] = v;
            sorted[i] = v;
        }

        Arrays.sort(sorted);

        HashMap<Integer, Integer> map = new HashMap<>(n * 2);
        int rank = 0;
        for (int i = 0; i < n; i++) {
            if (i == 0 || sorted[i] != sorted[i - 1]) {
                map.put(sorted[i], rank++);
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(map.get(origin[i]));
            if (i + 1 < n) sb.append(' ');
        }
        System.out.print(sb);
    }
}

시간·공간 복잡도

방법 1

시간 복잡도: 대략 O(NlongN)
- 중복 제거 O(N)
- 유니크 정렬 O(U log U)
- 매핑/출력 O(N)
- 단, Scanner와 split, Integer.valueOf 반복 호출로 체감 시간이 늘 수 있다.
공간 복잡도: O(N)

방법 2

시간 복잡도: O(N log N)
공간 복잡도: O(N)

어려웠던 점

처음 시행착오에서는 정렬된 유니크 리스트에서 순위를 얻기 위해 arrList.indexOf(num) 같은 방식으로 접근했는데, 이 경우 TimeOut이 발생한다.
- 이유는 원소마다 리스트를 선형 탐색하게 되어 전체가 최악 O(N²) 로 커질 수 있었기 때문이다.
결국 “값의 순위를 찾는 과정”은 반복 탐색이 아니라, HashMap으로 값→순위를 미리 만들어서 즉시 조회해야 한다는 점이 핵심이었다.
추가로, 입력이 커질 때 Scanner + split 조합이 병목이 될 수 있다는 점도 체감할 수 있는 포인트였다.