[정렬] 1427번 : 소트인사이드 - Java

2025/1/20 월요일

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

 

문제풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

// 소트인사이드
// 배열의 index를 key로 활용
// 계수 정렬 알고리즘 (Counting Sort)
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] arr = new int[10]; // index 10개 : [0,1,2,3,4,5,6,7,8,9]
        char[] temp = br.readLine().toCharArray();

        for (char c : temp) {
            int num = Integer.parseInt(String.valueOf(c));
            arr[num]++;
        }

        for (int i = 9; i >= 0; ) {
            if (arr[i] != 0) {
                System.out.print(i);
                arr[i]--;
            } else {
                i--; // arr[i]가 0인 경우, i 감소
            }
        }
    }
}

처음 제출한 코드는 계수 정렬을 활용해 문제를 풀었다.

계수 정렬은 배열에 데이터가 말 그대로 몇 번 나왔는지 counting 하며 이를 인용해 정렬하는 방식이다.

문제에서 수의 범위는 0~9까지라 크기가 10인 배열을 먼저 선언했다.

예제 입력 4에 있는 500613009를 입력하고 디버깅을 통해 arr 배열을 확인하면 각 인덱스에 해당하는 숫자의 개수를 알 수 있다. 숫자 0이 4개, 숫자 1이 1개, 숫자 3이 1개,.... 숫자 9가 1개
결과적으로 예제 출력 4값인 964310000이 출력된다.

 

import java.io.*;
import java.util.Arrays;

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

        String N = br.readLine();

        char[] arr = N.toCharArray();

        Arrays.sort(arr);

        for (int i = arr.length -1; i >=0; i--) {
            System.out.print(arr[i]);
        }

    }
}

 

참고자료를 보면 다양하게 풀 수 있는 방법들이 많았다.

정렬에 대해서 다시 한 번 짚고 넘어가야겠다. 또한 정렬 관련된 문제들을 오랜만에 모아서 다 풀어봐야겠다.

---

참고자료

https://st-lab.tistory.com/109

계수 정렬 : https://st-lab.tistory.com/104

https://velog.io/@hansung1459/%EC%A0%95%EB%A0%AC-%EA%B3%84%EC%88%98-%EC%A0%95%EB%A0%ACcounting-sort%EC%97%90-%EB%8C%80%ED%95%B4-%EC%95%8C%EC%95%84%EB%B3%B4%EC%9E%90