99클럽 코테 스터디 7일차 TIL + 정렬 (Collection.sort)

백준

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

18110번: solved.ac

---

• 오늘의 학습 키워드 : 정렬 (Collection.sort)
• 공부한 내용 본인의 언어로 정리하기
  

  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.ArrayList;
  import java.util.Collections;
  import java.util.List;
  
  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());
      List<Integer> arr = new ArrayList<>();
      for (int i=0; i<N; i++) arr.add(Integer.parseInt(br.readLine()));
      Collections.sort(arr);
  
      int excludingNumber = (int) Math.round(N * 0.15);
      // 상위 15%, 하위 15%를 제외한 새로운 배열 생성
      List<Integer> newArr = arr.subList(excludingNumber, N - excludingNumber);
      int sum = 0, average = 0;
  
      for (int a : newArr) sum += a;
      average = (int) Math.round((double) sum / newArr.size());
  
      System.out.println(average);
    }
  }​

• 오늘의 회고
  • mergeSort 분할정복정렬로 문제를 풀면 시간 제한(1초)에 맞출 수 있을 줄 알았는데 시간 초과됐다.
    너무 복잡하게 생각한 것 같아서 Collection.sort 내장 정렬 메서드를 사용해서 해결했다.

 

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

public class Main {
  static int[] arr;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());
    arr = new int[N];
    for (int i=0; i<N; i++) arr[i] = Integer.parseInt(br.readLine());
    mergeSort(0, N-1);

    int excludingNumber = (int) Math.round(N * 0.15);
    int[] newArr = Arrays.copyOfRange(arr, excludingNumber, N-excludingNumber); // 상위 15%, 하위 15%를 제외한 새로운 배열 생성
    int sum = 0, average = 0;

    for (int i=0; i<newArr.length; i++) sum += newArr[i];
    average = (int) Math.round((double) sum / newArr.length);

    System.out.println(average);
  }

  public static void merge (int left, int right) {
    int mid = (left + right) / 2;
    int i = left;
    int j = mid + 1;
    int c = left;
    int[] tmp = new int[arr.length];

    while (i <= mid && j <= right) {
      if (arr[i] <= arr[j]) {
        tmp[c++] = arr[i];
        i++;
      } else if (arr[i] > arr[j]) {
        tmp[c++] = arr[j];
        j++;
      }
    }

    while (i <= mid) tmp[c++] = arr[i++];
    while (j <= right) tmp[c++] = arr[j++];
    for (int k=left; k<=right; k++) arr[k] = tmp[k];
  }

  public static void mergeSort (int left, int right) {
    if (left != right) {
      int mid = (left + right) / 2;
      mergeSort(left, mid);
      mergeSort(mid+1, right);
      merge(left, right);
    }
  }
}​

 

---

99클럽 1기를 수강하면서 작성한 글입니다.

https://99club.oopy.io/

99클럽-1기 모집 중