백준) (자바) 1427 소트인사이드(선택 정렬로 풀어보기)

소트인사이드

 

소트인사이드 - 백준 -

1427번: 소트인사이드

---

내림차순으로 수를 한 줄에 연속적으로 정렬하면 되는 문제이다.

---

이번 문제는 선택 정렬(Selection Sort)로 풀어보고자 한다.

 

Selection Sort : 대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법이다.

 

시간복잡도는 O(n²)으로 느린편이다.

 

선택 정렬 과정

1. 정렬하는 과정에서 정렬되지 않는 남은 정렬 부분에서 최솟값 또는 최댓값을 찾는다.
2. 남은 정렬 부분에서 가장 앞에 있는 데이터와 선택한 데이터를 swap 한다.
3. 가장 앞에 있는 데이터의 위치를 변경하고 남은 정렬 부분의 범위를 축소한다.
4. 남은 정렬 부분이 없어질 때까지 반복한다.

 

위의 이미지처럼 앞에서부터 정렬이 되어간다.

for (int i = 0; i < numArrLen; i++) {
    max = i;

    for (int j = i + 1; j < numArrLen; j++) {
        if (numArr[j] > numArr[max]) max = j;
    }

    if (numArr[i] < numArr[max]) swap(numArr, i, max);
}

 

내림차순으로 앞에서부터 정렬할 것이므로 최댓값을 찾아주었다.

 

남은 배열에서 최댓값의 인덱스를 찾은 다음,

조건문으로 해당 남은 배열의 최대 값과 위치를 바꾸어준다.

 

---

Selection Sort로 풀어보기

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.stream.IntStream;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        String strNum = br.readLine();

        int[] numArr = IntStream.range(0, strNum.length())
                .map(strNum::charAt)
                .map(i-> i - '0').toArray();

        selectionSort(numArr);
        Arrays.stream(numArr).forEach(sb::append);
        System.out.println(sb);
    }

    private static void selectionSort(int[] numArr) {
        int numArrLen = numArr.length;
        int max;
        for (int i = 0; i < numArrLen; i++) {
            max = i;

            for (int j = i + 1; j < numArrLen; j++) {
                if (numArr[j] > numArr[max]) max = j;
            }

            if (numArr[i] < numArr[max]) swap(numArr, i, max);
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

---

---

Stream으로 정렬해 보기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.stream.IntStream;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        String strNum = br.readLine();

        int[] numArr = IntStream.range(0, strNum.length())
                .map(strNum::charAt)
                .map(i-> i - '0')
                .boxed()
                .sorted(Comparator.reverseOrder())
                .mapToInt(Integer::intValue)
                .toArray();

        Arrays.stream(numArr).forEach(sb::append);
        System.out.println(sb);
    }
}

---

---

Arrays.sort()로 풀어보기

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        String strNum = br.readLine();

        int strNumLen = strNum.length();
        Integer[] numArr = new Integer[strNumLen];
        for (int i = 0; i < strNumLen; i++) {
            numArr[i] = strNum.charAt(i) - '0';
        }

        Arrays.sort(numArr, Comparator.reverseOrder());

        Arrays.stream(numArr).forEach(sb::append);
        System.out.println(sb);
    }
}

---