문제설명
문제분석
1 이상 1,000만 이하의 숫자가 입력으로 주어지며 각 수는 1만 이하의 자연수이다. 입력받은 숫자들을 횟수만큼 오름차순으로 차례대로 출력해야하는 문제이다. 입력받은 후 Arrays.sort()를 이용해 풀면 간단하게 풀릴 문제라고 생각한 반면, 정렬 함수를 사용하지 않고, 입력받은 수의 가장 큰 수로 새로운 배열을 만들어 카운트를 이용해서 풀 수 있겠다고 생각했다. 구상한 방법은 다음과 같다.
- 입력 값을 저장할 1차원 배열을 생성
- 1차원 배열에 입력받은 값을 저장함과 동시에 최대 값을 비교
- 입력받은 숫자 내에서 최대 값의 길이 + 1만큼의 새로운 배열을 생성
- 앞서 저장된 배열을 순회하며 각 배열 요소를 새로운 배열의 인덱스로 활용하여 카운트 증가
- 마지막으로 새로운 배열은 순회하며 요소가 0이 아니면 해당 요소의 카운트만큼 인덱스를 반복하여 출력
슈도코드
실제로 코드를 짜기 전에 한글로 먼저 간단히 정리해보고 시작하겠다.
(안그러면 머리가 안돌아가거든요...)
int 숫자카운트 = 버퍼리더 활용
int 최대값 = 정수형 최소값 초기화
int[] 배열1 = 숫자카운트만큼 생성
for 0부터 숫자카운트 - 1까지 반복 {
// 각 요소 저장
배열1[인덱스] = 입력숫자
최대값 = Math.max이용
}
int[] 배열2 = 최대값 + 1만큼 생성(0을 제외하기 위함)
for 0부터 배열1의 길이만큼 반복 {
// 각 숫자의 자리에 카운트를 증가
배열2[배열1[index]]++;
}
for 0부터 배열2의 길이만큼 반복 {
if 해당 인덱스가 0이 아니면 {
for 0부터 현재 요소의 카운트만큼 반복 {
현재 인덱스 + "\n" 누적
}
}
}
출력실제코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n]; // 입력 숫자를 저장할 배열
int max = Integer.MIN_VALUE; // 입력 숫자 중 최대값
// 최대 값 확인 및 입력숫자 저장
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(br.readLine());
max = Math.max(max, arr[i]);
}
// 최대 값만큼 배열 생성
// +1은 입력받은 숫자와 인덱스를 맞춰주기 위함(굳이...?)
int[] arr2 = new int[max + 1];
for (int i = 0; i < arr.length; i++) {
// 입력받은 숫자를 인덱스로 하여 해당 인덱스의 카운트 증가
// ex) arr[i] = 3면 arr2[3]의 카운트를 증가
arr2[arr[i]]++;
}
// 카운팅된 배열에서 0이 아닌 요소를 반복하며 출력데이터 저장
for (int i = 0; i < arr2.length; i++) {
if (arr2[i] != 0) {
for (int j = 0; j < arr2[i]; j++) {
sb.append(i).append("\n");
}
}
}
System.out.println(sb.toString());
}
}마무리
Arrays.sort()와 카운팅 정렬
기본적으로 Java의 Arrays.sort()는 Dual-Pivot Quicksort 알고리즘을 사용하며, 평균과 최악 시간복잡도는 O(n log n)이다. 일반적으로 모든 범위의 알고리즘에 안정적인 성능을 보이고, 값의 범위가 매우 크거나 분포가 고르게 되어있는 경우 효율적으로 사용이 가능하다.
그에 반에 카운팅 정렬은 O(n + k)의 시간 복잡도를 가지고, 넓은 범위에서 사용할 경우 추가 메모리 사용이 많아져 비효율적이게 된다. 이번 문제처럼 1,000만 이하의 데이터라면 괜찮지만 1억 이상이 되는 경우 Arrays.sort()를 사용하는 것이 더 효율적이다. 또한, 데이터의 분포가 고른 경우에는 상관없지만 특정 범위에 집중되지 않고 분산이 심한 경우에도 비효율적이다.
카운팅 정렬 알고리즘을 기준으로 요약하면 다음과 같다.
장점
• 시간복잡도 : 제공된 코드의 시간복잡도는 O(n + k)로, k가 작다면 매우 효율적, 특히 값의 범위가 작은 경우 Arrays.sort()를 사용하는 것보다 빠를 수 있다. 예를 들어, 데이터의 값이 1부터 1,000만 사이의 정수이고 데이터의 개수가 많을 때 효율적.
• 메모리 효율성: k가 크지 않다면 추가 메모리 사용이 많지 않아 효율적.
단점:
• 범위 제한: 값의 범위가 매우 크다면 메모리 사용량이 급격히 증가할 수 있다. 예를 들어 값이 1부터 1억 사이의 정수라면 k가 매우 커져 비효율적.
• 데이터의 분포: 데이터가 특정 범위에 집중되지 않고 매우 분산되어 있다면 역시 비효율적일 수 있다.
참고로 Collections.sort()는 팀정렬 알고리즘을 사용한다고 하네요. Collections.sort()의 단점은 객체형 데이터를 다룰 때 추가 메모리의 효율성에 따라 비효율적일 수 있으니 참고하세요!
전체 소감
처음에는 Arrays.sort()를 이용해서 풀었지만 수행시간이 생각보다 오래걸려서 다른 방법을 생각한게 카운팅 정렬 알고리즘이었다. 오랜만에 스스로 생각해서 구현한 방법으로 문제를 풀어서 수행시간이 향상된 것을 보고 굉장히 짜릿한 경험을 했다.
정렬 알고리즘은 여러가지 방법이 있지만 그 중 어떤 것을 선택해서 사용해야하는지는 데이터의 범위, 형태, 분포 등을 확인하고 적합한 시간 복잡도를 가진 알고리즘을 사용하는 연습을 많이 해야할 것 같다.
