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

https://www.acmicpc.net/problem/1427

배열을 내림차순으로 정렬하는 문제로, 각 자리의 숫자가 붙어있을 때 각 자릿수을 어떻게 구분하여 정렬할지 생각해보는 문제이다.

Python

파이썬은 문자열 처리에 매우 강력한 언어라서 그냥 list형태로 받으면 알아서 구분해준다...

정렬도 그냥 sort() 함수 쓰면 되지만 N의 최댓값도 1,000,000,000으로 크지 않아 선택 정렬을 사용해보도록 하겠다.

선택 정렬이란 배열에서 최댓값(또는 최솟값)을 찾은 후, 이를 제외한 나머지 데이터 범위에서 가장 앞에 있는 데이터와 swap하는 것이 핵심이다.

선택정렬 알고리즘 순서를 나열하려면 아래와 같다.

1. 정렬해야할 범위 안에서 가장 앞부분 원소의 인덱스 저장
2. for문을 통해 1번에서 저장한 인덱스에 해당하는 값과 모두 비교하여 최댓값(or 최솟값) 저장
3. 정렬해야할 범위 안에서
   가장 앞부분 원소 < 최댓값 인덱스 원소 인경우 swap
4. 1, 2, 3번 과정을 배열 길이만큼 반복

N = list(map(int, input()))

# 선택정렬 알고리즘 사용
# 문제에서는 내림차순을 요구하므로 최댓값 저장
for i in range(len(N)):
    # 정렬해야할 범위 안에서
    # 가장 앞부분 원소의 인덱스 저장
    Max = i
    for j in range(i + 1, len(N)):
        # 내림차순 정렬이므로 앞부분 원소보다 더 큰 값이 존재하는지 비교
        if N[j] > N[Max]:
            Max = j

    # 정렬해야할 범위 안에서 가장 앞부분 원소보다
    # 최댓값을 가리키는 원소가 더 큰 경우 swap
    if N[i] < N[Max]:
        temp = N[i]
        N[i] = N[Max]
        N[Max] = temp


for i in range(len(N)):
    print(N[i], end='')

Java

자바의 경우 문자열을 처리하는 부분만 별도로 처리해주면 파이썬과 동일하다. 우선 입력값을 String으로 입력 받은 다음, substring(start_index, end_index - 1)을 통해 배열에 저장하면 된다.

그 이후 알고리즘은 동일하다.

1. 정렬해야할 범위 안에서 가장 앞부분 원소의 인덱스 저장
2. for문을 통해 1번에서 저장한 인덱스에 해당하는 값과 모두 비교하여 최댓값(or 최솟값) 저장
3. 정렬해야할 범위 안에서
   가장 앞부분 원소 < 최댓값 인덱스 원소 인경우 swap
4. 1, 2, 3번 과정을 배열 길이만큼 반복

import java.util.Scanner;

public class P_1427 {
    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(); i++) {
            int max = i;
            for (int j = i + 1; j < str.length(); j++) {
                if (A[max] < A[j]) {
                    max = j;
                }
            }

            if (A[max] > A[i]) {
                int temp = A[i];
                A[i] = A[max];
                A[max] = temp;
            }
        }

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