[선택정렬] 내림차순으로 자릿수 정렬

목차

1. 풀이

(1) 문제

백준 1427, 소트인사이드 : https://www.acmicpc.net/problem/1427

 

핵심키워드

- 시간 제한 2초

- N은 1,000,000,000보다 작거나 같은 자연수

- 내림차순 정렬

 

(2) 풀이

- 입력크기가 10자리로 제한되어 있기 때문에 O(n²) 알고리즘도 2초 내에 충분히 동작한다.

- 비효율적이지만 학습을 위해 선택정렬 알고리즘(O(n²))을 활용해 문제를 풀어본다.

 

선택 정렬(Selection Sort)

- 선택 정렬은 대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법이다.

- 시간 복잡도는 O(n2)이며 효율적이지 않아 자주 쓰이진 않는다.

- 선택 정렬 시간 복잡도

Best	O(n2)
Worst	O(n2)
Average	O(n2)

 

선택정렬 (예제)

1) arr {20, 12, 10, 15, 2} 인 배열을 오름차순으로 정렬해보자

 

2) 첫번째 스텝 - 전체 값 중에 최소값을 찾고, 제일 왼쪽에 있는 인덱스 값과 최소값의 인덱스 값을 스왑한다.

 

3) 두번째 스텝 - 첫번째 요소는 제외하고 나머지 요소에서 최소값을 찾고, 두번째 요소의 인덱스 값과 최소값의 인덱스 값을 스왑한다.

4) 나머지 - 나머지 스텝에서 위 과정을 반복해서 배열을 오름차순으로 정렬한다. 

2. 정답

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        int[] A = new int[str.length()];

        // 배열 입력
        for (int i = 0; i < str.length(); i++) {
            A[i] = Integer.parseInt(str.substring(i, i + 1));
        }

        //선택 정렬
        for (int i = 0; i < str.length(); i++) {
            int Max = i;
            for (int j = i + 1; j < str.length(); j++) {
                if (A[j] > A[Max]) {
                    Max = j;
                }
            }
            // 스왑 
            if (A[i] < A[Max]) {
                int temp = A[i];
                A[i] = A[Max];
                A[Max] = temp;
            }
        }

        //출력
        for(int i=0; i<str.length(); i++){
            System.out.print(A[i]);
        }


    }
}

• 내림차순이므로 최대값을 구해 스왑해야한다. (오름차순은 최소값)
• 배열 입력 부분에서 입력된 수를 숫자로 직접 받는 거보다 문자로 받아 substring하는 것이 더 쉽다.
• 선택 정렬은 이중 for문을 사용하고 스왑 알고리즘을 사용한다.

3. 참고

- Do it 알고리즘 코딩 테스트 자바 편(김종관)

- 선택 정렬 이미지 출처 : https://www.programiz.com/dsa/selection-sort