[백준 알고리즘] - 10989번

수 정렬하기3

나는 이 문제를 자바로 풀었다.

Problem
문제는 간단하다. 입력한 숫자 개수만큼 오름차순으로 정렬을 하는것이다.
나는 이 문제를 ArrayList로 Collections.sort로 문제를 풀려하였다.
그런데 자꾸 메모리초과, 시간초과가 나는 것이다. Array로 Arrays.sort로 문제를 푸니 문제가 해결 되었다. 문제는 ArrayList와 Array에 있는 것 같아서 둘의 차이점이 궁금하였다.

Array 와 ArrayList 차이

• Array는 초기화시 메모리에 할당되어 ArrayList보다 속도가 빠르다
• ArrayList는 데이터 추가 삭제시 메모리를 재할당하기 때문에 속도가 Array보다 느리다.
• ArrayList는 Default 저장용량은 10이다.
• ArrayList의 capacity가 배열의 길이와 같아지면 일반적으로 기존의 용량 + 기존 용량/만큼 크기가 늘어난 배열에 기존의 배열을 Copy한다.

그래서 ArrayList로 문제를 풀때는 메모리 초과가 나온것이다.

나는 ArrayList에 Default 저장용량은 없을줄 알았고 배열의 길이가 같아질 때 하나의 요소만큼 늘어날 줄 알았다.

Arrays.sort와 Collections.sort의 차이

둘의 정렬방식은 다르다

arrays.sort는 평균: O(nlong(n) 최악: O(n^2)
Collections.sort는 평균 , 최악: O(nlong(n))

코딩 테스트를 풀때 ArrayList를 사용할때는 좀 더 주의하면서 써야겠다.

Array-vs-ArrayList