[알고리즘_코딩 테스트_JAVA] 선택 정렬 (JAVA, PYTHON)

본문은 알고리즘 코딩테스트 자바편을 정리한 내용입니다 :)

 

✔ 문제 017 내림차순으로 자릿수 정렬하기

문제 바로가기 💨 

 

⬜ 핵심 아이디어

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

선택 정렬은 구현 방법이 복잡하고, 시간 복잡도도 O(n^2)으로 효율적이지 않아 코딩테스트에서는 많이 사용하지 않는다. 

슈도코드 작성하기

str(정렬할 수)
A(자릿수별로 구분해 저장한 배열)
for(str의 길이만큼 반복하기) {
    A 배열 저장 -> str.substring 사용하기
}

for(i: 0~str의 길이만큼 반복하기){
    for(j: i + 1 ~ str의 길이만큼 반복하기) {
        현재 범위에서 Max 값 찾기
    }
    현재 i의 값과 Max값 중 Max 값이 더 크면 swap 수행하기
}
A 배열 출력하기기

 

JAVA

import java.util.*;
import java.lang.*;
import java.io.*;

// Please name your class Main
class Main {
	public static void main (String[] args) throws java.lang.Exception {
	    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]);
	    }
	}
}

PYTHON

arr = list(map(int,input()))

for i in range(len(arr)):
    max = i
    for j in range(i+1,len(arr)):
        if arr[j]>arr[max]:
            max = j # 내림차순이므로 최댓값을 찾음
    arr[i],arr[max] = arr[max],arr[i]
for i in arr:
    print(i,end="")