백준 JAVA11 1427번 : 소트인사이드

Mention : 최대값이나 최소값을 찾아 SWAP하면 Selection sort ✅ , Max & temp 가 포인트이다.

소트인사이드

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	67496	43316	36249	64.537%

문제

배열을 정렬하는 것은 쉽다. 수가 주어지면, 그 수의 각 자리수를 내림차순으로 정렬해보자.

입력

첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 자리수를 내림차순으로 정렬한 수를 출력한다.

예제 입력 1

2143

예제 출력 1

4321

예제 입력 2

999998999

예제 출력 2

999999998

예제 입력 3

61423

예제 출력 3

64321

예제 입력 4

500613009

예제 출력 4

965310000

출처

• 문제를 번역한 사람: baekjoon
• 빠진 조건을 찾은 사람: bvba, djm03178

슈도 코드

N(정렬할 수 개수)
A(N을 자리수로 분리한 배열)
N을 한자리씩 분리해서 배열에 입력
for(N만큼 i++) {
	int 최대값;
	for(반복횟수 - i;j++) {
		if(A[j+1]>A[j]) {
		최대값 = A[j+1];
		A[j+1] = A[j];
		A[j] = 최대값;
		}
	}
	//출력
}

First Try

• Bubble sort

package sort;

import java.util.Scanner;

public class P1427_selectionSort {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		int N = Integer.parseInt(s);
		int[] A = new int[s.length()];

		for (int i = 0; i < s.length(); i++) {
			A[i] = Integer.parseInt(s.substring(i, i + 1));
		}

		for (int i = 0; i < s.length(); i++) {
			int max = A[i];
			for (int j = 0; j < s.length() - 1 - i; j++) {
				if (A[j + 1] > A[j]) {
					max = A[j + 1];
					A[j + 1] = A[j];
					A[j] = max;
				}
			}
		}
		for (int i = 0; i < s.length(); i++) {
			System.out.print(A[i]);
		}
	}
}

Refactoring

• Selection sort

package sort;

import java.util.Scanner;

public class P1427_selectionSort {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		int N = Integer.parseInt(s);
		int[] A = new int[s.length()];

		for (int i = 0; i < s.length(); i++) {
			A[i] = Integer.parseInt(s.substring(i, i + 1));
		}

		for (int i = 0; i < s.length(); i++) {
			int max = i;
			for (int j = i + 1; j < s.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 < s.length(); i++) {
			System.out.print(A[i]);
		}
	}
}