정렬 (3) 썸네일형 리스트형 [Java] Arrays.sort(), Collections.Sort() 속도 비교 알고리즘 문제를 풀며 이론적으로는 $O(n\log n)$의 시간 복잡도를 가진다고 알고 있던 정렬 함수들이 컬렉션의 종류에 따라 같은 코드지만 시간 차이가 많이 나는 것을 보고 실제 시간이 얼마나 차이 나는지 알아보기 위해 테스트를 진행해 보았다. 하는김에 PriorityQueue와 TreeMap도 얼마나 걸리는지 궁금해서 함께 테스트했다. 모두 같은 코드로 구성되어 있으며, 테스트데이터만 변경하면서 실험해 보았다. 같은 데이터로 10회 반복해 평균을 낸 시간을 정리했다. 버전 : Java 15 코드 : Github 테스트 데이터 : 출처 - Startlink/boj-sort-test 1️⃣ 이미 정렬되어있는 데이터 1부터 10,000,000까지의 숫자가 오름차순 정렬되어있는 데이터 2️⃣ 역순으로 정렬.. [백준] 18870번: 좌표 압축 - JAVA 🔗 문제 링크 BOJ 18870번: 좌표 압축 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 📝 풀이 과정 예시를 통해 문제를 먼저 이해했다. // 입력 2 4 -10 4 -9 // 출력 2 3 0 3 1 문제를 보면 현재 좌표보다 작은 좌표들의 개수가 압축값이 되고, 좌표 값이 같은 여러 개의 좌표가 있어도 1개로 취급하는 것을 알 수 있다. int[] sortNums = nums.clone(); Arrays.sort(sortNums); Arrays.sort.. [백준] 11399번: ATM - JAVA 🔗 문제 링크 BOJ 11399번: ATM 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 📝 풀이 과정 사람들이 번호 순서대로 줄을 선 상태이고, [3, 1, 4, 3, 2]의 인출시간이 걸린다고 했을 때, 아래만큼의 시간이 각각 소요되게 된다. 0번 : 3= 3 1번 : 3 + 1= 4 2번 : 3 + 1 + 4= 8 3번 : 3 + 1 + 4 + 3= 11 4번 : 3 + 1 + 4 + 3 + 2= 13 -------------------------------------- 총 인출 시간 : 3 + 4 + 8 + 11 + 13 = 39 .. 이전 1 다음
