[코딩테스트] 백준 1427 자바

백준 1427

백준 1427 문제

import java.util.*;

public class Boj1427 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.next(); // 문자열로 숫자를 받는다.
        int[] arr = new int[str.length()]; // 문자열 길이만큼 정수 배열을 만든다.

        for (int i = 0; i < str.length(); i++) {
            arr[i] = Integer.parseInt(str.substring(i, i + 1)); // substring(i, i+1)로 문자열을 숫자로 변환하여 배열에 담는다.
        }

        for (int i = 0; i < arr.length - 1; i++) {
            int max = i; // i값을 최대값으로 둔다.
            for (int j = i + 1; j < arr.length; j++) { // i의 다음 값부터 반복을 한다.
                if (arr[j] > arr[max]) { // 다음 수가 지금의 수보다 크다면
                    max = j; // 최댓값을 바꿔준다.
                }
            }
            if (max != i) { // 최댓값이 바꼈다면, i의 수와 최댓값의 수를 swap한다.
                int temp = arr[i];
                arr[i] = arr[max];
                arr[max] = temp;
            }
        }

        for (int i : arr) {
            System.out.print(i);
        }
    }
}

풀이

주어진 수의 각 자리수를 내림차순으로 정렬하는 문제인데 최대값이 10자리이기에 시간 복잡도O(n2)을 사용해도 무당하기에 선택 정렬을 사용해서 풀어보겠다.

1. 문자열로 주어진 수를 받는다.
2. 문자열 길이만큼 정수 배열을 만들다.
3. substring(i, i + 1)를 통해 각 자리수의 수를 추출하고 정수형으로 변환하여, 배열에 담는다.
4. 선택 정렬은 루프 당 최대값을 구하여, 앞에서부터 차례대로 swap을 하며 정렬하기 때문에 2중 반복문을 사용해야 한다.
5. 마지막 인덱스의 값은 알아서 정렬이 되기 때문에 arr.length-1만큼만 반복하며, i의 값을 max에 담는다.
6. 두 번째 반복문은 i의 다음 값인 i+1로 시작하는 j의 값이 max의 값보다 크면 max의 값은 j로 바꾼다.
7. 그렇게 한 루프를 돌면 max에는 가장 큰 값의 인덱스가 들어가 있으므로 i의 값과 max의 값을 스왑해준다.