[백준] 11582: 치킨 TOP N - JAVA

in Algorithm on 정렬

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

풀이

구간을 나눠 정렬해주면 되는 간단한 문제였다.

N/k 길이 씩 구간을 정해 그 구간을 정렬하여 출력한다.

임시로 배열이나 리스트를 만들고 구간의 값을 넣은 뒤 정렬해주었다.

임시로 저장할 공간을 만들 때 세가지 경우를 실험해 보았다.

  1. 배열을 매번 새로 선언.

  2. 리스트를 전역으로 선언하고 매번 list를 clear.

  3. 리스트를 매번 새로 선언.

배열을 매번 선언하는 것이 메모리, 시간이 모두 적게 나왔다.

리스트의 clear를 이용하는 것보다 매번 선언하는 것이 시간이 적게 걸렸다.

리스트의 clear함수는 리스트를 돌면서 null로 채우는 방식인데 list의 사이즈가 클 때는 clear보다 새로 선언하는 것이 더 빠르다.

배열 선언

메모리: 131752KB

시간: 1304ms

언어: Java 11

코드

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

public class Main {
    static int N;
    static int[] arr;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int k = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i += (N / k)) {
            doSort(i, i + N / k);
        }

        System.out.println(sb);
    }

    private static void doSort(int start, int end) {
        int[] tmp = new int[end - start];
        for (int i = start; i < end; i++) {
            tmp[i - start] = arr[i];
        }
        Arrays.sort(tmp);
        for (int i = 0; i < end - start; i++) {
            sb.append(tmp[i]).append(" ");
        }
    }

}

리스트 clear

메모리: 181588KB

시간: 1480ms

언어: Java 11

코드

static List<Integer> tmp = new ArrayList<>();

private static void doSort(int start, int end) {
    for (int i = start; i < end; i++) {
        tmp.add(arr[i]);
    }
    Collections.sort(tmp);
    for (int i = 0; i < end - start; i++) {
        sb.append(tmp.get(i)).append(" ");
    }
    tmp.clear();
}

리스트 선언

메모리: 204832KB

시간: 1456ms

언어: Java 11

코드

private static void doSort(int start, int end) {
    List<Integer> tmp = new ArrayList<>();
    for (int i = start; i < end; i++) {
        tmp.add(arr[i]);
    }
    Collections.sort(tmp);
    for (int i = 0; i < end - start; i++) {
        sb.append(tmp.get(i)).append(" ");
    }
}