[2750] 수 정렬하기

✔ 수 정렬하기

[백준 2750]

문제 분석하기

N의 범위가 1000으로 매우 작기 때문에 O(N²)의 시간 복잡도를 갖는 버블 정렬 알고리즘을 이용해도 해결 가능

손으로 풀어보기

1. 비교 연산이 필요한 루프 범위를 설정
2. 인접한 데이터 값을 비교
3. swap 조건에 부합하면 swap 연산을 수행
4. 루프 범위가 끝날 때까지 2~3을 반복
5. 정렬 영역을 설정한 후, 다음 루프를 실행할 때는 이 영역을 제외
6. 비교 대상이 없을 때까지 1~5를 반복

슈도코드 작성하기

N(정렬할 수 개수)
A(정렬할 배열 선언)
for(루프의 개수만큼 반복)
{
    for(정렬하는 범위만큼 반복)
    {
        현재 A 배열의 값보다 1칸 오른쪽 배열의 값이 더 작으면 두 수 바꾸기
    }
}
A 배열 출력

코드 구현하기

/**
 * 2750) 수_정렬하기
 */
public class D015_2750 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // N(정렬할 수 개수)
        int N = sc.nextInt();
        // A(정렬할 배열 선언)
        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++) {
                // 현재 A 배열의 값보다 1칸 오른쪽 배열의 값이 더 작으면 두 수 바꾸기
                if (A[j] > A[j + 1]) {
                    int temp = A[j];
                    A[j] = A[j + 1];
                    A[j + 1] = temp;
                }
            }
        }
        // A 배열 출력
        for (int i = 0; i < N; i++) {
            System.out.println(A[i]);
        }
    }
}