자바(Java) 알고리즘 문제풀이 위에서 아래로 [이코테 / 정렬]

 

 

 

---

 

 

문제 설명

하나의 수열에는 다양한 수가 존재한다. 이러한 수는 크기에 상관없이 나열되어 있다.

이 수를 큰 수부터 작은 수의 순서로 정렬해야 한다. 수열을 내림차순으로 정렬하는 프로그램을 작성하시오.

 

 

입력 조건

첫 번째 줄에 수열에 속해 있는 수의 개수 N이 주어진다. (1 <= N <= 500)

두 번째 줄부터 N + 1번째 줄 까지 N개의 수가 입력된다. 수의 범위는 1 ~ 100,000 이하의 자연수이다.

 

 

출력 조건

입력으로 주어진 수열이 내림차순으로 정렬된 결과를 공백으로 구분하여 출력한다.

동일한 수의 순서는 자유롭게 출력해도 괜찮다.

 

 

풀이 코드

가장 기본적인 정렬을 할 수 있는지 묻는 문제이다. 자바의 컬렉션 정렬 라이브러리는 최악의 상황에서도 O(nlogn) 의 시간복잡도를 보장하는데, 이런 문제에서는 정렬 라이브러리가 아닌, 직접 구현을 해보도록 하자. 

수의 개수가 500 개 이하이므로 어떤 정렬 알고리즘을 구현해도 상관없고 선택 정렬과 삽입 정렬을 구현해서 풀이한다.

또한 아래 풀이는 오름차순이 아닌 내림차순으로 정렬을 구현한 것 !

 

선택 정렬

배열을 차례로 탐색하면서 최소값을 지닌 인덱스의 원소와 기준 원소를 비교하고, 서로 교환하는 식으로 구현한다.

기본적으로 이중 반복을 사용하기 때문에 O(N^2) 의 시간복잡도를 지니는데, 데이터가 많지 않다면 쓸만하지만 별로 쓸 일은 없는 듯..

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++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        // 1. 선택 정렬
        // 선택 정렬은 배열을 차례로 탐색하면서 기준 원소와 배열 중 가장 작은 수를 찾아 서로 바꾸는 식으로 구현한다.
        // 내림차순은 반대로 .
        for (int i = 0; i < n - 1; i++) {
            int minIdx = i; // 인덱스 기억

            // 배열에서 가장 큰 값을 지닌 인덱스 찾기
            for (int j = i + 1; j < n; j++) {
                // 더 큰 값이라면 ?
                if (arr[j] > arr[minIdx]) {
                    minIdx = j; // 해당 인덱스 기억
                }
            }

            int tmp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = tmp;
        }

        System.out.println(Arrays.toString(arr));
    }
}

 

 

 

삽입 정렬

배열의 [1] 인덱스부터 앞으로 넘어가며 탐색하는데, 현재 선택된 원소가 이전 원소보다 큰 경우, 그리고 인덱스 0까지 비교한다.

이중 반복문을 사용했기 때문에 기본적으로 O(N^2) 의 시간복잡도를 가지지만, 삽입 정렬의 특징으로 거의 정렬된 상태에서는 O(N) 의 

시간복잡도를 가진다. 따라서 거의 정렬된 상태로 배열이 주어진다면 삽입 정렬을 사용하는 것이 좋다.

package this_is_coding_test.sort;

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

public class 위에서_아래로_Remind {
    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++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        // 2. 삽입 정렬
        // [1] index 부터 시작하고, 내부 반복문은 1씩 감소하는 형태로 구현한다.
        for (int i = 1; i < n; i++) {
            int tmp = arr[i];
            int prev = i - 1;

            // 현재 선택된 원소가 이전 원소보다 큰 경우까지 반복 (내림차순)
            while (prev >= 0 && arr[prev] < tmp) {
                arr[prev + 1] = arr[prev];
                prev--;
            }

            // 탐색 종료된 지점에 현재 선택된 변수의 값을 삽입
            arr[prev + 1] = tmp;
        }

        System.out.println(Arrays.toString(arr));
    }
}