[백준] 10989 - 수 정렬하기 3 (JAVA/ 자바)

10989번 문제(1)

10989번 문제(2)

 

일단 Arrays.sort()를 이용하여 문제를 해결할 수 있긴 하다.

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 N = Integer.parseInt(br.readLine());
    int[] list = new int[N];
    
    for(int i=0; i<N; i++){
        list[i] = Integer.parseInt(br.readLine());
    }
    Arrays.sort(list);
    for(int i: list){
        sb.append(i).append("\n");
    }
    System.out.println(sb);
    br.close();
    }
}

 

 

문제 힌트에 카운팅 정렬이 언급되기 때문에 카운팅 정렬에 대해 찾아보았다. 

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

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

이 분의 글을 참고하였다.

 

참고하면서 공부한 것까지는 좋았는데, 실제로 문제에 대입하는 과정에서 누적합을 사용하니까 10000까지 출력되는 문제가 발생했다... 코드를 이것저것 고쳐보았지만 결국 해결하지 못해서, 코드를 참고하였다...

 

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

[백준] 10989번 : 수 정렬하기 3 - JAVA [자바]

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());
    //수의 범위가 1~10000
    int[] range = new int[10001];
    
    //해당 값을 인덱스로 하는 배열 값 증가
    for(int i=0; i<N; i++){
        range[Integer.parseInt(br.readLine())]++;
    }

    for(int i = 1; i < 10001; i++){
        while(range[i] > 0){
            sb.append(i).append('\n');
            range[i]--;
        }
    }
    System.out.println(sb);
    br.close();
    }
}

코드를 보니 누적합 부분은 제외하시고, 숫자가 1부터 10000까지 들어가는 것을 고려하여 10001까지 for문을 돌리고 while문을 사용하여 range[i]이 0보다 클 경우 데이터를 추가해나가는 것을 알 수 있었다.