[java 백준]실버 5/ 10989번 수 정렬하기 3

https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
public class Main {
 
    public static int n;
 
    public static int[] counting;
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine());
 
        counting = new int[10001];
 
        for (int i = 0; i < n; i++) {
            counting[Integer.parseInt(br.readLine())]++;
        }
 
        StringBuilder sb = new StringBuilder();
 
        for (int i = 1; i < 10001; i++) { // 배열에 들어오는 수는 1이상부터임
            for (int j = 0; j < counting[i]; j++) {
                sb.append(i + "\n");
            }
        }
        bw.write(sb.toString());
        bw.close();
        br.close();
    }
 
}

 

 

이 문제는 시간제한과 메모리 제한이 까다롭기 때문에 입력받을때는 절대 Scanner를 쓰면 안된다. BufferedReader 사용해야한다. 

나는 자꾸 시간초과가 떠서 BufferedWriter도 사용했다.

또한 배열할당할 때 동적할당하면 에러뜨기 때문에 counting = new int[10001];  --> 이런식으로 미리 배열의 크기를 정해주면 좋다. 

 

정렬하는 방법 중에서 퀵정렬보다도 빠르다는 카운팅정렬을 이용했다.

 

카운팅 정렬

---

https://st-lab.tistory.com/104

자바 [JAVA] - 카운팅 정렬 (Counting Sort / 계수 정렬)

 

Stranger'sLAB님의 블로그를 보며 카운팅정렬을 공부해봤다.

 

카운팅정렬이란 다른 배열들처럼 원소를 가지고 비교하는 것이 아닌 원소가 몇번 등장했는지 인덱스를 가지고 오름차순으로 정렬한다. 

 

카운팅 정렬은 누적합을 이용해서 인덱스끼리 정렬한다. 하지만 누적합을 이용하면 메모리 제한에 걸리기 때문에 이 아이디어를 사용해서 더 단순하게 풀어보겠다.

누적합을 이용해서 10989번을 푸는 아이디어는 뒤에 정리해뒀다...!(스크롤을 더 내리면 된다)

 

예를 들어 숫자가 5 2 3 1 4 2 3 5 1 7 , 총 10개가 들어온다고 해보자.

그러면 

 counting[Integer.parseInt(br.readLine())]++; 

를 하고 counting 배열을 살펴보면

 

 

예를 들어 coutning[1]=2라는 것은 1이 입력값들 중 2번 들어있다는 것을 의미한다. 

그럼 여기서 count[index]값이 0인애들을 제외하고 index들을 출력하면 오름차순으로 정렬이 될 것이다. 

 

for (int i = 1; i < 10001; i++) { // 배열에 들어오는 수는 1이상부터임

            for (int j = 0; j < counting[i]; j++) {

                sb.append(i + "\n");

            }

        }

 

우선 겉에 있는 for문으로 counting배열의 인덱스 끝까지 탐색하고, 안에 있는 배열의 경우 

만약 counting[6] 같이 값이 0이면 포함되지 않고,

counting[1]=2처럼 값이 0보다 크면 

1

1

이런식으로 포함되게 된다. 

 

for문 대신 while문을 써도 된다.

 

while (counting[i] > 0) {
   sb.append(i + "\n");
   counting[i]--;
} 

 

대신 counting[i]--; 이걸 써주지 않으면 무한루프를 돌 것이다. 

 

카운팅정렬 원리 이해 

---

앞에 예를 들었던 것 처럼 자가 5 2 3 1 4 2 3 5 1 7 , 총 10개가 들어온다고 해보자.

 

그러면 입력받는 숫자를 저장해주는 배열 arr 이 있을 때

 

숫자가 몇개 들어있는지 저장해놓은 Counting 배열은

이 counting배열은 누적합 해줄 것인데

counting[i]+=counting[i-1]; 을 따른다

 

그러면 counting[3]은 2에서 4가 된다.

뒤에있는 다른 수도 누적합을 적용해주면 

 

이제부터는 복잡해진다. 

 

 

Arr[9]=7 그러면 7이 counting배열(누적합 적용해준거)의 index값으로 들어간다. Counting[7]=9 인데 여기서 1을 빼준다.

1을 뺀 8이 Result의 인덱스 값으로 들어가고 Counting에서 인덱스였던 7이 Result[8]의 값으로 들어간다. 

 

2,3,5 같이 숫자가 중복이면 1을 더 빼줘야 한다.

 

3의 경우를 보자

 

arr[8]일때 counting[1]=2-1이 됐지만 이 1에서 다시 1을 빼주면 된다.

그러면 0값이 Result[0]으로 가게 되고 Counting에서 인덱스였던 1은 Result[0]의 값으로 들어가게된다. 

최종적으로