[hackerrank] counting sort 1 계수정렬 누적합 배열 만들기

[문제 링크]

https://www.hackerrank.com/challenges/countingsort1/problem?isFullScreen=true

Counting Sort 1 | HackerRank

 

public class CountingSort1 {
    public static void main(String[] args) {
        List<Integer> arr = Arrays.asList(1, 1, 3, 2, 1);
        counting(arr);
    }

    public static List<Integer> counting(List<Integer> arr) {
        int[] answer = new int[100];

        for (int i = 0; i < 101; i++) {
            for (int j = 0; j < arr.size(); j++) {
                if (arr.get(j) == i) {
                    answer[i]++;
                }
            }
        }
        output(answer);

        List<Integer> answerList = new ArrayList<>();
        for (int i = 0; i < answer.length; i++) {
            answerList.add(answer[i]);
        }
        return answerList;
    }

    public static void output(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

 

 

계수 정렬 알고리즘에서 누적합 배열만 만들면 되는 문제.

계수 정렬의 시간복잡도와 공간복잡도에 대한 것은 다음 문제에서 더 직관적으로 느낄 수 있을 것 같다.

처음엔 계수 정렬을 머릿 속에서만 이해하려고 하니 바로 이해가 되지 않았는데, 아래 링크를 보니 이 알고리즘을 바로 이해할 수 있었다!

 

https://www.cs.miami.edu/home/burt/learning/Csc517.091/workbook/countingsort.html

Counting Sort