백준/JAVA
[JAVA] 백준_2751
영초_
2023. 7. 28. 04:53
[문제]
2751번: 수 정렬하기 2
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
www.acmicpc.net
단순하게 Arrays.sort(배열)을 썼다가 시간초과가 나왔다. 그래서 찾아보니 Collections 인터페이스의 sort 함수를 이용하면 시간복잡도가 훨씬 줄어든다는 것을 알았다. [백준] 2751번 : 수 정렬하기 2 - JAVA [자바] (tistory.com) 이 분의 풀이를 참고했다. Collections (컬렉션)은 제네릭 기법을 사용하기 때문에 Collections.sort(배열) 이런 식으로 매개변수에 그냥 배열을 대입하면 안 되고, List<T> 타입의 매개변수를 사용해야 한다.
[풀이]
Collections.sort를 사용하기 위해 ArrayList<Integer>타입의 객체를 생성하여 매개변수 자리에 넣어주었다.
이 풀이는 시간이 1500ms가 나왔지만, boolean타입의 배열을 이용해 시간복잡도를 더 줄일 수 있는 풀이도 있었다.
시간이 거의 절반 줄었다.