[백준/Java] 18870번 좌표 압축

-Code

 ✅ 실패한 코드1

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

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());

        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] pointArr = new int[n];
        List<Integer> pointList = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            int point = Integer.parseInt(st.nextToken());
            pointArr[i] = point;
            // 중복 제거
            if (!pointList.contains(point)) {
                pointList.add(point);
            }
        }
        // 정렬
        Collections.sort(pointList);
        StringBuilder answer = new StringBuilder();
        for (int point : pointArr) {
            // 배열의 원소가 정렬된 위치의 어디에 있는지 찾기
            answer.append(pointList.indexOf(point))
                    .append(" ");
        }

        System.out.println(answer);
    }
}

 ✅ 실패한 코드2

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

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());

        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] pointArr = new int[n];
        List<Integer> pointList = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            int point = Integer.parseInt(st.nextToken());
            pointArr[i] = point;
            // 중복 제거
            if (!pointList.contains(point)) {
                pointList.add(point);
            }
        }
        // 정렬
        Collections.sort(pointList);
        StringBuilder answer = new StringBuilder();
        for (int point : pointArr) {
            // 배열의 원소가 정렬된 위치의 어디에 있는지 찾기
            answer.append(binarySearch(pointList, point))
                    .append(" ");
        }

        System.out.println(answer);
    }
    // 이분 탐색
    private static int binarySearch(List<Integer> list, int target) {
        int start = 0, end = list.size() - 1;

        while (start <= end) {
            int middle = (start + end) / 2;
            if (list.get(middle) == target) {
                return middle;
            }
            if (list.get(middle) > target) {
                end = middle - 1;
            } else {
                start = middle + 1;
            }
        }
        return -1;
    }
}

✅ 성공한 코드

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

public class BOJ18870 {
    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[] pointOrigin = new int[n];

        for (int i = 0; i < n; i++) {
            pointOrigin[i] = Integer.parseInt(st.nextToken());
        }
        // 복사 및 정렬
        int[] sortedPoints = pointOrigin.clone();
        Arrays.sort(sortedPoints);
        // 맵을 통해 key, value로 저장
        Map<Integer, Integer> sortedIndexMap = new HashMap<>();
        int nowIndex = 0;
        for (int val : sortedPoints) {
            if(!sortedIndexMap.containsKey(val)) {
                sortedIndexMap.put(val, nowIndex);
                nowIndex++;
            }
        }

        StringBuilder answer = new StringBuilder();
        for (int point : pointOrigin) {
            // 배열의 원소가 정렬된 위치의 어디에 있는지 찾기
            answer.append(sortedIndexMap.get(point))
                    .append(" ");
        }

        System.out.println(answer);
    }
}

파이이분탐색도 실패해서 원인을 찾아보니 아래와 같았습니다.

1. pointList.contains

• 중복을 제거하기 위한 List.contains()는 내부적으로 리스트의 처음부터 끝까지 하나씩 확인하는 선형 탐색(O(N))을 때문에 루프 안에서 N번 반복합니다. 그래서 중복 제거 과정에서만 O(N^2)의 시간이 제한 시간(2초)을 아득히 초과

2. List.get(middle)

• ArrayList는 인덱스 접근이 빠르지만, 전반적인 자료구조 관리 비용이 배열보다 크기때문에 이 문제처럼 대량의 데이터를 다룰 때는 int[] 배열을 직접 사용하는 것이 더 유리