[Algo] 백준 11582 치킨 TOP N JAVA

문제 바로가기 : https://www.acmicpc.net/problem/11582

메모리 : 314496KB

시간 : 2140ms

언어 : Java 11

---

코드

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

public class Main {
    static int[] chicken;
    static int N;
    static List<Integer> tmp;

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

        // k명 남은 상태가 몇번째 턴인지 알아보기
        int t = 0;
        while (true) {
            if ((N >> t) == k) {
                break;
            }
            t++;
        }

        tmp = new ArrayList<>();

        for (int n = 2; n < N; n *= 2) {
            if (t == 0) {
                break;
            }
            // n개를 정렬
            sorting(n);
            t--;
        }
        StringBuilder sb = new StringBuilder();
        for (int i : chicken) {
            sb.append(i).append(" ");
        }
        System.out.print(sb);
    }

    private static void sorting(int n) {
        for (int i = 0; i < N; i += n) {
            for (int j = i; j < i + n; j++) {
                tmp.add(chicken[j]);
            }
            Collections.sort(tmp);
            for (int j = i, idx = 0; j < i + n && idx < tmp.size(); j++, idx++) {
                chicken[j] = tmp.get(idx);
            }
            tmp.clear();
        }
    }
}

풀이

치킨집 N은 항상 2의 제곱이기때문에 비트마스크를 이용해 k명의 사람이 정렬을 수행할 때가 몇 번째 턴인지 알아낼 수 있다.
sorting함수에 몇 개씩 잘라서 정렬할 것인지(n)을 넣어주고 계산한다.

더 좋은 풀이

list를 선언하고 clear해주는 것이 메모리적으로 유리할것이라고 생각했는데 실제로는 그렇지 않았다..! clear가 빠른연산이 아니라는 것은 알고있었지만 5초라는 넉넉함에 사용해보았다. int배열을 사용할때마다 새로 만들어주는 것이 훨씬 메모리가 적게 들었다.
clear는 배열을 돌면서 값을 null로 채우기때문에 시간적으로도, 공간적으로도 부적합한것 같다.
아래의 풀이가 메모리, 시간적으로 유리하다.

---

메모리 : 189500KB

시간 : 1640ms

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static int[] chicken;
    static int N;
    static int[] tmp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        chicken = new int[N];
        for (int i = 0; i < N; i++) {
            chicken[i] = Integer.parseInt(st.nextToken());
        }
        int k = Integer.parseInt(br.readLine());
        // k명 남은 상태가 몇번째 턴인지 알아보기
        int t = 0;
        while (true) {
            if ((N >> t) == k) {
                break;
            }
            t++;
        }
        for (int n = 2; n < N; n *= 2) {
            if (t == 0) {
                break;
            }
            // 2개를 정렬
            sorting(n);
            t--;
        }
        StringBuilder sb = new StringBuilder();
        for (int i : chicken) {
            sb.append(i).append(" ");
        }
        System.out.print(sb);
    }

    private static void sorting(int n) {
        tmp = new int[n];
        for (int i = 0; i < N; i += n) {
            for (int j = i, idx = 0; j < i + n && idx < n; j++, idx++) {
                tmp[idx] = chicken[j];
            }
            Arrays.sort(tmp);
            for (int j = i, idx = 0; j < i + n && idx < n; j++, idx++) {
                chicken[j] = tmp[idx];
            }
        }
    }
}