[알고리즘] 선택 정렬

선택 정렬이란?

• 대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법
• 구현이 복잡한 편이고 시간 복잡도도 n^2로 좋지 않은 편이다.
  

---

실전! 문제 풀이(백준 1427)

import java.util.*;

class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        String input = sc.next();
        int[] parsedInput = new int[input.length()];
        for(int i=0;i<parsedInput.length;i++){
            parsedInput[i] = Integer.parseInt(input.substring(i,i+1));
        }
        for(int i=0;i<parsedInput.length;i++){
            int maxIndex=i;
            for(int j=i+1;j<parsedInput.length;j++){
                if(parsedInput[j]>parsedInput[maxIndex]){
                    maxIndex=j;
                }
            }
            if(parsedInput[i]<parsedInput[maxIndex]){
                int temp = parsedInput[i];
                parsedInput[i]=parsedInput[maxIndex];
                parsedInput[maxIndex]= temp;
            }
            System.out.print(parsedInput[i]); 
        }               
    }
}

얻어갈 점:

• 처음에 주어진 입력값 n이 1,000,000,000이기에 정렬 알고리즘의 시간 복잡도를 생각했을때 선택정렬을 적용하지 못할거라 생각했지만 출력을 보면 주어진 n을 자리수로 보는 것이기에 실질적 n의 크기는 10이여서 모든 정렬 알고리즘이 사용 가능했다.
• string의 길이 => length() , 배열의 길이 => legnth, collection의 크기 =>size()
• string 자르는 방법 : substring or split("")