[백준] 1427번 소트인사이드 - 내림차순 정렬 / 선택정렬

문제

 

 

로직

정렬하려는 수 입력 받기

정렬하려는 수와 같은 길이의 문자열 선언

배열 선언

double형 변수 선언 

최댓값 인덱스 변수 선언 및 초기화

 

1. 반복문

- 정렬하고자하는 변수의 자릿수별로 doulbe형 변수에 저장

(Math.pow()는 double형으로 반환함)

- 배열에 저장한 값을 정수형으로 변환 후 차례대로 저장

 

2. 반복문

- 최댓값 초기화

- 3. 반복문

   -  배열에서 최댓값 찾아서 저장

   - if문 -> 최댓값과 배열의 값이 같을 때 -> 그때의 인덱스 값 저장

- 최댓값과 배열의 값 스왑하기

 

4. 반복문

- 내림차순 정렬된 배열의 값 순서대로 출력 

 

 

My Code

import java.io.*;

public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(bf.readLine());
String numStr = Integer.toString(N);
int [] numArray = new int[numStr.length()];
double num;
int maxIndex = 0;

for (int i = numArray.length - 1; i >= 0; i--)
{
num = N % (Math.pow(10, i+1)) / (Math.pow(10, i));
numArray[i] = (int)num;
}

for(int i = 0; i < numArray.length ; i++){
int max = 0;
for (int j = i; j < numArray.length; j++){
max = Math.max(numArray[j], max);
if (max == numArray[j]) maxIndex = j;
}
int temp = numArray[i];
numArray[i] = numArray[maxIndex];
numArray[maxIndex] = temp;
}
for(int a:numArray){
System.out.print(a);
}
}
}

 

 

문제의 핵심 및 알게된 점

선택정렬을 이용하여 내림차순 정렬이 가능한 문제이다.

N의 값이 1~1,000,000,000까지의 범위인데 이때 N은 자릿수이기 때문에 10자리인 10을 의미한다.

따라서 시간복잡도가 O(n^2)인 선택정렬를 이용해도 된다.

최댓값을 찾고 인덱스를 스왑하는 것이 핵심인 문제이다.

 

 

참고 강의_인프런의 Do it! 알고리즘 코딩테스트 with JAVA