BOJ_1427 : 소트인사이드

 

👉 문제링크

1427번: 소트인사이드

---

---

🔸 문제 분석 🔸

• N이 1~10억으로 주어지고, 각 자리수로 내림차순 정렬해 출력한다.
• 10개의 수를 내림차순 정렬하는 것이므로 제한시간 2초(약 2억회 계산)까지는 여유롭다.

🔸 코드 🔸

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str[] = br.readLine().split("");
        Arrays.sort(str, Collections.reverseOrder());
        for (String s : str){
            System.out.print(s);
        }
    }
}

🔸 코드 해석 🔸

• 한 줄 입력받고 split으로 각 자리수를 String 배열에 나눠 담는다.
• 내림차순 정렬 후 붙여서 출력한다.

🔸 다른 풀이 🔸

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        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()-1; 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]);
        }
    }
}

• 교재의 선택정렬을 연습하기 위한 풀이
• 선택 정렬 과정
  1. 남은 정렬 부분에서 최솟값 또는 최댓값을 찾는다.
  2. 남은 정렬 부분에서 가장 앞에 있는 데이터와 선택된 데이터를 swap 한다.
  3. 가장 앞에 있는 데이터의 위치를 변경해(index++) 남은 정렬 부분의 범위를 축소한다.
  4. 전체 데이터 크기만큼 index가 커질 때까지, 즉 남은 정렬 부분이 없을 때까지 반복한다.
• 자연수를 받아 자릿수별로 정렬하는 문제이므로 먼저 숫자를 각 자릿수 별로 나누는 작업 필요
  • 나머지 연산으로 분리할 수 있지만, String값으로 받은 후 substring()함수를 이용해 자릿수 단위로 분리하고, 이를 다시 int형으로 변경해 배열에 저장
• 그 다음 단순하게 배열을 정렬
  • n이 크지 않으므로 내장 함수를 쓰지않고 선택 정렬 사용해서 내림차순 정렬

---

🔸 end 🔸

• 만들어진 메소드들로 편하게 풀이할 수 있었다.
• Arrays.sort의 내림차순은 헷깔려서 Collections.reverseOrder()인 걸 다시 확인했다.
• 선택정렬 연습을 위해 풀이를 추가했다.(22.11.08)