[백준] '수 정렬하기3' - Java

<문제 제시>

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

>> 주의사항 : 시간 제한

<예시 입출력>

---

<문제 해결 과정>

이번 문제는 시간제한(=시간복잡도 고려)도 있지만, 수의 범위가 매우 크기때문에 배열의 크기를 10001크기로 선언한다.

boolean배열로 선언하게 되면 중복으로 입력되는 데이터를 처리하기 힘들어진다. (인덱스로 접근하기 때문)

---

Answer 1) 

int[] arr = new int[10001];

// 자연수를 입력받고, 0도 제외된 데이터이므로 1부터 시작
for(int i = 1; i < arr.length; i++) {

    // arr에 입력된 데이터가 있는 경우에만, 그 값을 StringBuilder에 누적
    // StringBuilder에 누적시키면, 그만큼 arr은 카운트를 감소시킴
    while(arr[i] > 0) {
        //0이면 통과

        sb.append(i).append('\n');
        arr[i]--;
    }
}

 

최적의 정렬을 찾는 것인데, 수 정렬하기2에서 개선하여 인덱스에 해당숫자의 개수를 배열에 누적합하고, 그 값을 오름차순 정렬하여 출력한다. 

배열에 담기는 값은 1~10000까지 숫자 중 개수를 카운트하여 1부터 10000까지 인덱스에 ++하여 개수를 카운트 하는 것이다.

인덱스는 i이상부터 탐색한다. arr[i]를 감소시키며, while문을 돈다.

첫째줄에 수의 개수가 주어지고, 무작위로 숫자가 두번째줄부터 입력되어지면, 

배열에 Integer.parseInt(br.readLine())로 입력받고, 정수형 변환 후 ++하여 인덱스를 증가시킨다.

두번째줄부터 1씩 감소시키며, 0보다 클때까지 반복한다. 

10
5
2
3
1
4
2
3
5
1
7

이 입력데이터로 주어지면, 

[0, 2, 2, 2, 1, 2, 0, 1, 0, 0, 0... ]

0번부터 10번인덱스까지인데, 시작인덱스가 i = 1이므로 1번인덱스부터 탐색해보았을때, 

2에서 1이 2개란 의미이므로, StringBuilder에 1을 두번 쌓는다.

이 과정을 주어진 N의 범위만큼 반복한다.

---

<전체코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int[] arr = new int[10001];
		
		int N = Integer.parseInt(br.readLine());
		
		for(int i = 0; i < N; i++) {
			arr[Integer.parseInt(br.readLine())]++;
		}
		
		
		for(int i = 1; i < arr.length; i++) {
			
			while(arr[i] > 0) {
				//0이면 통과
				
				sb.append(i).append('\n');
				arr[i]--;
			}
		}
		
		System.out.println(sb);
	}

}

---

인덱스에 값의 개수를 카운트하여 푸는 방법을 생각하지 못하였다. 다른 풀이방법을 참고하여 이러한 방법도 있음을 공부할 수 있었고, boolean형으로 선언하여 중복체크를 하지 못할때 int형으로 배열을 선언해 중복까지 체크할 수 있음을 알 수 있었다.

---

문제링크)
https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3