[백준 1427] 소트인사이드 (JAVA)

백준 1427번 문제  - 소트인사이드

1427번: 소트인사이드

---

문제 분석

 

 

• 배열 정렬을 내림차순으로 해야한다

 

---

해결 키 포인트

 

• 오름차순일 경우는 Arrays.sort()를 사용하면 되지만, 내림차순일 경우는 Arrays.sort() 사용하기도 복잡하다
• 내림차순으로 정렬할 때, 선택 정렬 사용 - 선택 정렬이 시간복잡도가 효율적인건 아니나 위 문제는 조건 시간이 짧지 않으므로 가능

---

선택 정렬 설명

 

최솟값 또는 최댓값을 찾고, 남은 정렬 부분의 가장 앞에 있는 데이터와 swap하는 것이 선택 정렬의 핵심

 

Do it! 알고리즘 코딩 테스트 기본

 

---

코드

import java.io.*;

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

        // 수 입력
        String s = br.readLine();
        int [] nums = new int [s.length()];
        for(int i=0;i<s.length();i++) {
            nums[i] = s.charAt(i);
        }

        // 수 정렬
        for(int i=0;i<s.length();i++) {
            // i 이후부터 가장 큰 수 찾기
            int max = i;
            for(int j=i;j<s.length();j++) {
                if(nums[max] < nums[j]) {
                    max = j;
                }
            }

            // 가장 큰 수와 i번째 수와 바꾸기
            int temp = nums[i];
            nums[i] = nums[max];
            nums[max] = temp;

            // 출력
            bw.write(nums[i]);
        }
        bw.flush();
        bw.close();
    }
}