[선택 정렬] 백준 1427

 

 

선택 정렬이란?

대상 데이터에서 최대나 최솟값을 갖는 데이터를 선택하는 정렬이다.

선택 정렬은 구현 방법이 복잡하고, 시간 복잡도가 O(㎡)으로 효율적이지 않아 많이 사용하지는 않는다.

구현 방법은 최솟값 또는 최댓값을 찾고 남은 정렬에서 가장 앞에 있는 데이터와 swap하는 것을 반복하는 것이다.

 

예를 들어 최솟값을 기준으로 정렬할 때, 

1 3 2 5 4   -> 1과 5 비교 -> 1이 더 작음 -> 그대로 둠       : 남은 정렬 3 2 5 4 

1 3 2 5 4   -> 3과 2비교 -> 2가 더 작음 -> swap                : 남은 정렬 3 5 4

1 2 3 5 4   -> 3과 5비교 -> 3이 더 작음 -> 그대로 둠        : 남은 정렬 5 4 

1 2 3 5 4   -> 5와 4 비교 -> 4가 더 작음 -> swap

1 2 3 4 5    -> 완성!

 

 

백준 1427번에 적용해보기

 

/**
 * 백준 1427
 * 선택정렬로 풀어보기
 */

public class 내림차순으로_자릿수_정렬하기 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); //input값이 적으므로 버퍼리더 대신 스캐너 사용
        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 = 0l 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.println(a[i]);
        }
    }
}