자바 코딩테스트 강좌, 줄 세우기

이번 강좌에서는 자바를 이용한 취업 준비에 유용한 알고리즘 문제를 다룰 것입니다. 주제는 “줄 세우기”로, 이 문제를 통해 자료구조, 정렬 및 알고리즘의 기초적인 이해도를 높이고 실제 코딩테스트에서 활용할 수 있는 능력을 키울 수 있습니다.

문제 설명

주어진 학생들의 키를 기준으로 줄을 세우는 문제입니다. 서로 다른 키의 학생들을 줄 세우고 싶습니다. 즉, N명의 학생이 있을 때, 학생의 키 정보가 주어졌을 때, 이들을 키 순서대로 정렬해 출력하는 프로그램을 작성해주세요.

입력

첫 번째 줄에는 학생 수 N이 주어집니다. (1 ≤ N ≤ 100,000)
두 번째 줄에는 각 학생의 키가 공백으로 구분되어 주어집니다. (1 ≤ 키 ≤ 200)

출력

키 순서대로 학생의 키를 출력합니다.

예제 입력

5
170 165 180 175 160

예제 출력

160 165 170 175 180

문제 풀이 과정

1. 문제 이해하기

문제를 해결하기 위해 먼저 문제의 요구사항을 명확히 이해해야 합니다. 입력으로 주어진 학생들의 키를 정렬하여 출력해야 합니다. 입력의 크기가 클 수 있는 점을 고려하여 효율적인 정렬 알고리즘을 선택할 필요가 있습니다.

2. 알고리즘 선택

학생 수는 최대 100,000이며, 각각의 키 값은 1부터 200까지의 범위를 갖습니다. 이 경우, 저희는 비교 기반 정렬 알고리즘 중 하나인 퀵 정렬, 병합 정렬 등을 사용할 수 있지만, 키의 범위가 제한되어 있는 상황에서는 계수 정렬(Counting Sort) 알고리즘을 사용하는 것이 더 효율적입니다.

3. 계수 정렬 알고리즘 설명

계수 정렬은 O(N + k)의 시간복잡도로 정렬을 수행할 수 있으며, 여기서 k는 정렬할 데이터의 값의 범위입니다. 이 문제에서는 각 학생의 키가 1에서 200 사이의 정수이므로 k는 200이 됩니다. 계수 정렬의 과정은 다음과 같습니다:

각 키가 몇 번 나타나는지를 저장하기 위한 배열을 생성합니다.
입력된 키를 하나씩 읽어 해당 키의 인덱스를 증가시킵니다.
계수 배열을 통해 실제로 정렬된 값을 출력합니다.

4. 자바 코드 구현

아래는 위의 알고리즘을 바탕으로 작성한 자바 코드입니다:

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 학생 수 N 입력
        int N = scanner.nextInt();
        // 키 수를 담는 배열 선언 (1~200)
        int[] heightCount = new int[201];

        // 학생들의 키 입력 및 카운트
        for (int i = 0; i < N; i++) {
            int height = scanner.nextInt();
            heightCount[height]++;
        }

        // 정렬된 키 출력
        StringBuilder result = new StringBuilder();
        for (int i = 1; i <= 200; i++) {
            while (heightCount[i] > 0) {
                result.append(i).append(" ");
                heightCount[i]--;
            }
        }
        System.out.println(result.toString().trim());

        scanner.close();
    }
}

5. 코드 설명

위 코드에서, 입력된 학생 수를 기준으로 카운트 스위치 배열을 만들어 각 학생의 키를 인덱스별로 카운트합니다. 그런 다음, 카운트 배열을 순회하여 값이 존재하는 인덱스를 결과 문자열로 출력합니다.

6. 시간 복잡도

이 알고리즘의 시간 복잡도는 O(N + k) 입니다. N은 학생 수, k는 키의 범위입니다. 따라서, 이 알고리즘은 매우 효율적이며, 문제의 제약 조건을 만족하는 데 적합합니다.

결론

이번 강좌에서는 “줄 세우기” 문제를 계수 정렬 알고리즘을 사용하여 해결하는 방법을 배웠습니다. 이러한 기법은 키의 범위가 제한적이거나 쉽게 예측 가능한 상황에서 특히 유용합니다. 실제 코딩테스트에서 이와 유사한 문제를 접하게 될 가능성이 높으니, 자신만의 알고리즘 스킬을 더 발전시켜보세요!