[백준 BOJ 2750번] 수 정렬하기

출처 : https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기

 

1. 문제

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

---

2. 입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

5
5
2
3
4
1

---

3. 출력

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

1
2
3
4
5

---

4. 풀이

다양한 정렬들 중 기본 정렬인 선택 정렬, 버블 정렬, 삽입 정렬을 사용해서 풀 수 있다.

---

5. 소스코드

<선택 정렬>

 

import java.io.*;

class Main{
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        int [] arr = new int [num];

        for(int i=0; i<num; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }
        for(int i=num-1; i>0; i--){
            int max = arr[0];
            int idx = 0;
            for(int j=0; j<=i; j++){
                if(max< arr[j]){
                    idx = j;
                    max = arr[j];
                }
            }
            arr[idx] = arr[i];
            arr[i] = max;
        }

        for(int a: arr) System.out.println(a);
    }
}

<버블 정렬>

 

import java.io.*;

class Main{
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        int [] arr = new int [num];

        for(int i=0; i<num; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }
        for(int j=0; j<num-1; j++){
            for(int i=0; i<num-1-j; i++){
                int temp;
                if(arr[i] > arr[i+1]){
                    temp = arr[i];
                    arr[i] = arr[i+1];
                    arr[i+1] = temp;
                }
            }
        }

        for(int a: arr) System.out.println(a);
    }
}

<삽입 정렬>

 

import java.io.*;

class Main{
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        int [] arr = new int [num];

        for(int i=0; i<num; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }
        int key,i,j;
        for(j=1; j<=num-1;j++){
            key = arr[j];
            i = j-1;

            while(i>=0 && arr[i]>key){
                arr[i+1] = arr[i];
                i--;
            }
            arr[i+1] = key;
        }
        for(int a: arr){
            System.out.println(a);
        }
    }
}

---

6. 배운 것

정렬에 대해 문제를 풀기 전 미리 선택, 버블, 삽입 정렬에 대한 공부를 마친 후 접근하였다. 상대적으로 이해하기 어려웠던 삽입정렬을 여러 번 직접 코드를 작성하다보니 숙달되었고 앞으로 남은 타 정렬법들도 이해하며 코드로 직접 구현해보는 시간을 많이 가져야겠다.