
✔ 문제 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="")'자료구조&알고리즘 > 알고리즘_코딩테스트' 카테고리의 다른 글
| [알고리즘_코딩 테스트_JAVA] 퀵 정렬-K번째 수 구하기 (JAVA, PYTHON) (1) | 2024.01.23 |
|---|---|
| [알고리즘_코딩 테스트_JAVA] 삽입 정렬-ATM (JAVA, PYTHON) (0) | 2024.01.19 |
| [알고리즘_코딩 테스트_JAVA] 버블 소트 프로그램 1 (JAVA, PYTHON) (0) | 2024.01.01 |
| [알고리즘_코딩 테스트_JAVA] 수 정렬하기 1 (JAVA, PYTHON) (0) | 2023.12.27 |
| [알고리즘_코딩 테스트_JAVA] 절댓값 힙 구현하기 (JAVA, PYTHON) (1) | 2023.12.26 |