[do it 알고리즘] 백준 1427 (선택 정렬)

문제 설명

 

풀기 전 생각

• 선택 정렬은 O(N^2)의 시간 복잡도를 가짐
• 전체 round는 (배열크기 - 1)만큼 진행
• 배열의 가장 앞부분을 최댓값으로 미리 정함 arr [i]
• i+1부터 비교해 나가며 미리 정한 최댓값보다 큰 값이 나오면 최댓값 교체
• 가장 앞자리와 최댓값 swap
• i++ 해가며 차례대로 정렬

코드

import java.util.*;
public class Baek1427 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        int[] arr = new int[str.length()];

        for(int i = 0; i < arr.length; i++){
            arr[i] = str.charAt(i) - '0';
        }

        for(int i = 0; i < arr.length-1; i++){
            int max = arr[i];
            int maxIndex = i;
            for(int j = i+1; j < arr.length; j++){
                if(arr[j] > max){
                    max = arr[j];
                    maxIndex = j;
                }
            }
            if(arr[i] < arr[maxIndex]){
                swap(i,maxIndex,arr);
            }

        }

        for(int i =0;i<arr.length;i++){
            System.out.print(arr[i]);
        }
    }
    public static void swap(int a, int b, int[] arr){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

리뷰

코딩테스트에선 비효율적이라 잘 쓰지 않는다고 한다.
그래도 구현을 해보고 원리를 알아 면접 질문에 대비하자.