백준 10989번 수 정렬하기 3 자바 / 백준 단계별로 풀어보기 9단계 / 9. 정렬

백준 9단계 3번 문제 - 10989 수 정렬하기 3

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

10989번: 수 정렬하기 3

 

 

 

 

---

9. 정렬 (3) 백준 10989번 문제 수 정렬하기 3

---

문제

---

 

 

 

 

---

과정 생각해보기

---

 

단계 시작 전 한 줄로 언급되어 있듯 '카운팅 정렬'을 사용해 풀어야 한다

 

카운팅 정렬은 입력된 값이 있을 때,

카운트 배열의 인덱스 값 = 입력된 값이 되도록 하고 차례대로 그 숫자들을 출력하는 방식이다

 

보기 쉽게 예시로 설명하면 다음과 같다

 

 

배열 arr의 크기 5

배열 arr
인덱스 0	1	2	3	4
입력 숫자 1000	1000	1	4000	5000

 

 

배열 count의 크기 = 배열 arr의 최대수+1

배열 count
인덱스 0	1 …	1000 …	4000 …	5000
0	1	2	1	1

count의 인덱스 값 = arr에 입력된 값

배열 arr에서 1000이 2번 입력되었으므로 count[1000] = 2

 

 

(좀 더 촘촘하게 본 배열 count)

배열 count
인덱스 0	1	2	… 500	… 1000	…1500	… 3000	… 4000	… 4500	… 5000
0	1	0	0	2	0	0	1	0	1

배열 count[] = new int[5000]; 인 상황에서count[1] = 1count[1000] = 2count[4000] = 1count[5000] = 1입력값=인덱스값이어야 하므로 count 배열의 크기가 arr에서 입력된 최대값+1인 것(인덱스 번호는 전체 크기-1까지니까)

 

 

이 상태에서 값이 0인 인덱스들은 제외하고, 인덱스 값들을 그대로 출력하면

arr과 크기가 똑같은 새로운 배열 a는 다음과 같아진다

새로운 배열 a
인덱스 0	1	2	3	4
1	1000	1000	4000	5000

앞에 있는 인덱스값이 자동으로 먼저 출력되므로 따로 부등식 같은 조건을 주지 않아도 된다

 

 

 

---

오답

---

 

import java.io.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        int count[] = new int[10001];        //입력되는 숫자의 범위는 10_000까지
        
        for(int i = 0; i < n; i++) {
            count[Integer.parseInt(br.readLine())]++;    //count 함수의 인덱스 = 입력한 수
        }
        
        br.close();
        
        for(int i = 0; i < count.length; i++) {
            if(count[i] != 0) {        //해당 인덱스에 값이 있다면 = 사용자가 입력한 값이라면
                int j = 0;
                while(j < count[i]) {
                    System.out.println(i);
                    j++;
                }
            }
        }
    }
}

 

 이클립스에서 실행해보면 얼추 맞는 것 같은데 백준에서 시간초과가 뜬다

 

 

 

---

정답 인정 코드

---

 

(1)

import java.io.*;
 
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 count[] = new int[10001];        //입력되는 숫자의 범위는 10_000까지
        
        for(int i = 0; i < n; i++) {
            count[Integer.parseInt(br.readLine())]++;    //count 함수의 인덱스 = 입력한 수
        }
        
        br.close();
        
        for(int i = 1; i < count.length; i++) {    //문제에서 0은 입력하지 않아서 1부터 시작
            int j = 0;
            while(j < count[i]) {
                sb.append(i).append('\n');
                j++;
            
            }
        }
        System.out.println(sb);
    }
}

 

StringBuilder를 추가했더니 정답처리 되었다

 

 

 

(2)

import java.io.*;
 
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 count[] = new int[10001];        //입력되는 숫자의 범위는 10_000까지
        
        for(int i = 0; i < n; i++) {
            count[Integer.parseInt(br.readLine())]++;    //count 함수의 인덱스 = 입력한 수
        }
        
        br.close();
        
        for(int i = 1; i < count.length; i++) {    //문제에서 0은 입력하지 않아서 1부터 시작
            while(0 < count[i]) {    //해당 인덱스값이 입력되었다면
                sb.append(i).append('\n');    //인덱스값=입력값과 줄바꾸기를 결합
                count[i]--;            //1번 입력되었으므로 1번 줄인다
            }
        }
        System.out.println(sb);
    }
}

 

미세하긴 하지만 처리속도가 조금 더 빠른 방법이다

변수 j는 설정하지 않고 count[i]의 개수를 줄이는 방법이다

 

 

 

---

직후 백지 복습

---

 

import java.io.*;
 
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 count[] = new int[10001];
        
        for(int i = 0; i < n; i++) {
            count[Integer.parseInt(br.readLine())]++;
        }
        
        for(int i = 1; i < count.length; i++) {
            while(count[i] > 0) {
                sb.append(i).append('\n');
                count[i]--;
            }
        }
        
        System.out.println(sb);
    }
}

 

 

 

---

어려워보였던 카운팅 정렬도 직접 쳐보면서 하니까 이해도 잘 되고 재밌다