코딩 테스트 [정렬] - 수 정렬하기

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

---

입력

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

출력

1번째 줄부터 N개의 줄에 오름차순 정렬한 결과를 1줄에 1개씩 출력한다.

예제 입력
5	// 수의 개수
5
2
3
4
1

예제 출력
1
2
3
4
5

---

1단계 - 문제 분석하기

N의 최대 범위가 1,000으로 매우 작기 때문에 O(n2) 시간 복잡도 알고리즘으로 풀 수 있다. 버블 정렬 시간 복잡도가 O(n2)이므로 버블 정렬 알고리즘을 이용해 정렬해도 시간 복잡도 안에서 문제를 해결할 수 있다.

2단계 - 손으로 풀어 보기

3단계 - sudo코드 작성하기

N(정렬할 수 개수)
A(정렬할 배열 선언)

for(i : 0 ~ N-1) {
	for(j : 0 ~ N-1-i) {
    	현재 배열의 값보다 1칸 오른쪽 배열의 값이 더 작으면 두 수 바꾸기
	}
}

A 배열 출력

4단계 - 코드 구현하기

import java.util.Scanner;

public class Q15 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] A = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = sc.nextInt();
        }

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

        for(int i = 0; i < N; i++){
            System.out.println(A[i]);
        }
    }
}

---

• Do it! 알고리즘 코딩테스트 자바 편