[JAVA]BOJ 18870, 좌표 압축

처음엔 문제가 무슨 소린가했다.. 그냥 입력받은 수보다 작은 입력받은 수들의 개수를 구하는거다.

 

1. 배열 입력받기

2. 중복없이 정렬된 새 배열 만들기

3. 기존 배열의 값에 해당하는 새 배열의 인덱스값 출력하기

 

이렇게 구상했고, 테스트케이스로 예시를 들자면..

 2   4 -10  4  -9

[0] [1] [2] [3] [4]

1.배열을 입력받고, 2.정렬되고, 중복이 없는 새 배열을 만든다.

 2   4 -10  4  -9            -10 -9   2  4

[0] [1] [2] [3] [4]            [0] [1] [2] [3] 

  <기존 배열>               <새 배열>

3. 기존 배열의 값에 해당하는 새 배열의 인덱스 값을 출력한다.

기존 배열의 [0]2는 새 배열의 [2]2에 해당하고, 인덱스인 2를 출력한다.

기존 배열의 [1]4는 새 배열의 [3]4에 해당하고, 인덱스인 3를 출력한다.

기존 배열의 [2]-10는 새 배열의 [0]-10에 해당하고, 인덱스인 0를 출력한다.

기존 배열의 [3]4는 새 배열의 [3]4에 해당하고, 인덱스인 3를 출력한다.

기존 배열의 [4]-9는 새 배열의 [1]-9에 해당하고, 인덱스인 1를 출력한다.

 

그럼 결과는 2 3 0 3 1 이 될 것이다.

 

이 문제의 N의 범위는 1<=N<=1,000,000 이다. 시간 제한은 2초이다. 1.은 상수시간, 2.은 arrays.sort 를 이용하면 되니 시간복잡도는 O(NlogN)이다.  1,000,000 * log1,000,000 은 대략.. 6,000,000이므로 2초 안에 계산이 가능하다. 그렇다면 3.을 잘 구현하면 문제없이 통과할 수 있을것이다.

 

3.을 구현하는 방법은 두 가지가 있는데 이중 for문을 사용해 직접 검색을 하는 것이다. 그러나 이렇게 하면 O(logN^2) = 약 1,000,000,000,000 이 되므로 2초 안에 계산을 할 수 없다. 그러니 더 빠른 방법으로 검색을 해야한다. 대중적으로 많이 사용하는 .BinarySearch(이진탐색)을 이용했다. 이진탐색 자체는 O(logN)이고 모든 Xi(원래 배열 값들)에 대해 확인해야 하므로 O(NlogN)이 될것이다. 그리고 결과적으로 2와 3을 각각 1번씩 하므로 O(2NlogN)이 될 것이다. 이렇게 하면 문제없이 시간안에 계산이 끝날것이다.

 

인 줄 알았는데.. 입출력시 버퍼리더랑 버퍼라이터를 써야한다는 것을 잠시 잊었다. 시간이 타이트해서 꼭 BufferedReader, BufferedWriter를 사용해야 한다. 그리고 BufferedWriter 작동방식이 버퍼에 데이터를 담아뒀다가 출력하는 방식이라서 반복문에서 일일히 출력할 필요가 없다. 처음에 그거 모르고 System.out 처럼 일일히 출력했더니 시간초과가 나더라..

---

아래는 전체 코드이다.

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ18870 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N, i;
        String str;
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());

        int[] arr = new int[N];
        int[] sortedArr = new int[N];

        str = br.readLine();
        st = new StringTokenizer(str);
        for(i=0;i<N;i++){
            arr[i] = Integer.parseInt(st.nextToken());
            sortedArr[i] = arr[i];
        }

        // 중복없이 저장한 배열 만들기 -> 정렬 먼저 필요
        Arrays.sort(sortedArr); // 정렬하기
        sortedArr = Arrays.stream(sortedArr).distinct().toArray(); // 중복 제거하기, 스트림으로 변환 후 중복 요소 제거,를 다시 배열로 변환


        // 이진탐색으로 값 같은거 찾기 -> O(nlogn)
        for(i=0;i<N;i++){
            bw.write(Arrays.binarySearch(sortedArr, arr[i]) + " ");
//            bw.flush(); // 시간초과함
        }
        bw.flush();
        bw.close();
    }
}

중복없이 정렬된 새 배열을 만들때 어떻게 코드를 짤 까 고민했는데, gpt가 간단한 방법을 알려줬다.

 

• Arrays.stream(newArr): 배열 newArr를 스트림으로 변환합니다. 스트림은 일련의 요소들을 순차적으로 처리할 수 있는 유틸리티로, 배열이나 컬렉션의 데이터를 효율적으로 처리할 수 있게 합니다.
• .distinct(): 스트림에서 중복 요소를 제거합니다. 내부적으로는 Set을 사용하여 중복을 필터링합니다.
• .toArray(): 중복이 제거된 요소들을 배열로 다시 변환합니다. 스트림의 최종 연산으로, 스트림의 모든 요소를 수집하여 새로운 배열을 생성합니다.
• 추가 설명 첨부 : https://velog.io/@yun8565/Java-%EC%8A%A4%ED%8A%B8%EB%A6%BCStream-%EC%A0%95%EB%A6%AC