문제

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

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    br.readLine();
    Integer[] array = convertStringArrayToIntegerArray(br.readLine().split(" "));
    List<Integer> list = Arrays.asList(array.clone());

    Collections.sort(list);

    Map<Integer, Integer> map = new HashMap<>();
    int index = 0;
    for (int i : list) {
        if (!map.containsKey(i)) {
            map.put(i, index++);
        }
    }

    StringBuilder sb = new StringBuilder();
    for (int i : array) {
            sb.append(map.get(i)).append(" ");
    }

    System.out.println(sb.toString());
}

private static Integer[] convertStringArrayToIntegerArray(String[] args) {
    Integer[] array = new Integer[args.length];
    int i = 0;
    for (String str : args) {
        array[i++] = Integer.parseInt(str);
    }

    return array;
}

흐름

  1. 입력받은 좌표를 저장한 리스트로 수정하면 출력 순서를 맞출 수 없으니 우선 좌표 list를 복사한다.
  2. 복사한 list를 정렬하고 순서대로 반복하면서 좌표값을 key로 index를 저장한다.
    1. {-10 : 0}, {-9, 1}… {4,4}
  3. 입력받은 좌표를 순서대로 반복하면서 map에 key로 index를 가져온다.
  4. 끝

좌표 압축의 이유

좌표 {2 4 -10 4 -9} 압축 전
좌표 {2 4 -10 4 -9} 압축 후
  • 문제의 예제인 좌표 {2 4 -10 4 -9}을 위와 같은 알고리즘으로 압축하면 {2 3 0 3 1}이 되는데 위 그림 처럼 압축된 점들도 같은 동일선상 안에 놓이게 된다.
  • 이렇게 범위가 매우 넓은 좌표의 경우에 좌표를 인덱싱해서 처리 할 경우 손쉽게 처리 할 수 있게 된다.

결과

참고 사이트