알고리즘 단계별로 풀어보기 : BOJ-10989(수정렬하기[3])

문제(출처)

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 

둘째 줄부터 N개의 줄에는 숫자가 주어진다. 

이 수는 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력

10

5

2

3

1

4

2

3

5

1

7

예제 출력

1

1

2

2

3

3

4

5

5

7

내 풀이

package date_20190115;

import java.io.BufferedReader;

import java.io.BufferedWriter;

import java.io.IOException;

import java.io.InputStreamReader;

import java.io.OutputStreamWriter;

public class BOJ_10989 {

    public static void main(String args[]) {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        

        try {

            int num = Integer.parseInt(br.readLine());

//           입력 할 값을 저장

            int[] arr = new int[num];

//          입력 할 값 만큼 배열 생성

            

            int max = 0;

            for(int i = 0; i < num; i++) {

                arr[i] = Integer.parseInt(br.readLine());

//              배열의 크기만큼 입력

                

                if(max < arr[i]) {

//                  가장 큰 값을 확인

                    max = arr[i];

                }

            }

            

            int[] count = new int[max+1];

//          가장 큰 값 만큼 count 배열 생성

            for(int i = 0; i < arr.length; i++) {

                count[arr[i]]++;

//              arr 배열에 저장 된 값을 기준으로 인덱스 증가

            }

            

            for(int i = 1; i < count.length; i++) {

                count[i] = count[i-1]+ count[i];

//              이전 값을 누적하여 저장

            }

            

            int[] tempArr = new int[num];

            

            int temp = 0;

            for(int i = arr.length-1; i >= 0; i--) {

                temp = arr[i];

//              arr 배열의 끝부터 확인

                tempArr[--count[arr[i]]] = temp;

//              arr 배열의 값을 count배열의 인덱스로 사용하고 count배열의 값을하나씩 줄여나가면서 정렬

            }

            for(int i = 0; i < tempArr.length; i++) {

                bw.write(String.valueOf(tempArr[i]));

                bw.newLine();

            }

            bw.close();

            

        } catch (NumberFormatException e) {

            e.printStackTrace();

        } catch (IOException e) {

            e.printStackTrace();

        }

        

    }

}

내 풀이 해석

배열의 인덱스와 배열의 값을 이용해서 카운팅하여 정렬하는 알고리즘입니다.

학습/검색

참고