백준 2750 - 수 정렬하기 1

YongHyun·2023년 4월 4일

Java 백준 코딩테스트

백준, 프로그래머스 - 코딩테스트

목록 보기

15/43

문제

시간제한 1초

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

입력

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

출력

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

예제 입력 1

5
5
2
3
4
1

N개의 수를 오른차순으로 정렬하면 되는 문제이다. N의 최대 범위는 1,000이기 때문에 $O^2$ 시간 복잡도 알고리즘으로도 풀 수 있다.

책에서는 버블 정렬을 이용하여 문제를 풀어보았기 때문에 여기서도 같은 방식으로 문제를 풀어보고 다른 방법으로도 설명해 보겠다.

버블 정렬

버블 정렬은 두 인접한 데이터의 크기를 비교해서 정렬하는 방법입니다. 시간 복잡도는 $O^2$ 으로 느린 편에 속한다.

먼저 {5, 2, 3, 4, 1} 배열에서 5와 2를 비교한다.

5가 더 크기 때문에 위치를 변경한다. {2, 5, 3, 4, 1}

다음 5와 3을 비교하면 5가 더 크기 때문에 위치를 변경한다. {2, 3, 5, 4, 1}

다음 5와 4를 비교하면 5가 더 크기 때문에 위치를 변경한다. {2, 3, 4, 5, 1}

다음 5와 1을 비교하면 5가 더 크기 때문에 위치를 변경한다. {2, 3, 4, 1, 5}

그러면 맨 오른쪽에 있는 5는 정렬이 완료되었기 때문에 다음 루프 부터는 5를 제외한 나머지 수들을 이용하여 정렬을 하면 된다.

이를 코드에 적용하면 다음과 같다.

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

public class 수정렬하기 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        for(int i = 0; i < N; i++) {
            int num = Integer.parseInt(br.readLine());
            arr[i] = num;
        }

        for(int i = 0; i < N; i++){
            for(int j = i + 1; j < N; j++) {
                if(arr[i] > arr[j]){
                    int tmp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tmp;
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < arr.length; i++){
            sb.append(arr[i] + "\n");
        }

        System.out.println(sb);


    }

}

이렇게 버블 정렬을 직접 구현하여도 맞는 답으로 나오지만 나는 Arrays.sort() 함수를 사용하여서 문제를 풀어보았다.

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

public class 수정렬하기 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];

        for(int i = 0; i < N; i++){
            int num = Integer.parseInt(br.readLine());
            arr[i] = num;
        }

        Arrays.sort(arr);

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < arr.length; i++){
            sb.append(arr[i]+"\n");
        }

        System.out.println(sb);


    }

}