21.08.20 기록

백준 알고리즘 2751 풀이

🎆나의 풀이(메모리 94.8MB, 시간 880ms로 통과)

-어제 풀이의 해설 방식으로 풀었다.
-Arrays.sort()는 아래 코드보다 더 오래걸렸고, 직접 구현한 정렬은 시간초과로 실패했다.

  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;

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

          int[] numbers = new int[N];
          for(int i = 0; i < N; i++) {
              numbers[i] = Integer.parseInt(br.readLine());
          }

          final int RANGE = 1_000_000;
          boolean[] check = new boolean[2 * RANGE + 1];

          for(int i = 0; i < N; i++) {
              check[Integer.parseInt(br.readLine()) + RANGE] =  true;
          }

          StringBuilder sb = new StringBuilder();
          for(int i = 0; i < check.length; i++) {
              if(check[i]) { sb.append(i-RANGE).append("\n"); }
          }
          System.out.println(sb);
      }
  }

🎆해설(메모리 166.3MB, 시간 1.74s로 통과)

-Arrays.sort()는 평균 복잡도가O(nlogn)이지만 최악의 경우 O(n²)이다.
-이 문제에서는 최악의 경우에도 O(nlogn)을 보장하거나, O(n)에 가까운 알고리즘을 사용해야 한다.
-아래는 Collections.sort()를 사용한 코드이다.

• Collections.sort()
  • 합병 정렬의 최악의 경우(O(nlogn))와 삽입 정렬의 최선의 경우(O(n))을 보장하는 timesort(합병x삽입)이다.
    
  • 이 정렬을 사용하려면 primitive 배열이 아닌 List 계열의 자료구조 배열을 사용해야 한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

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

        ArrayList<Integer> numbers = new ArrayList<>();
        for(int i = 0; i < N; i++) {
            numbers.add(Integer.parseInt(br.readLine()));
        }

        Collections.sort(numbers);

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < numbers.size(); i++) {
            sb.append(numbers.get(i)).append("\n");
        }
        System.out.println(sb);
    }
}