[백준] 수 정렬하기 (2750) - Java 자바

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

 

이전에 이미 풀었던 문제지만, 

https://sober-developer.tistory.com/90

알고리즘 3주 마스터 플랜 1주차

 

차근차근 푸는 연습을 위해 다시 풀어보겠다.

 

수 정렬하기

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

231248

133053

91129

58.261%

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력 1 복사

5
5
2
3
4
1

예제 출력 1 복사

1
2
3
4
5

 

✅ 이번 주 목표를 상기한다.

1. 문제 풀기 전에 접근법을 문장으로 적는 습관 들이기.
2. 하루 한 문제라도 반례 생성해서 직접 검증하기.
3. "이론 -> 문제 풀이 -> 오답 정리" 루틴을 실천하기.

문제 풀이 방식도 상기한다.

✅ 1단계: 문제 읽기 전 먼저 개념 확인

• 문제를 보고 바로 코드 작성 금지.
• 관련된 이론/유형을 먼저 떠올려 보기 (예: DFS/BFS 문제라면 탐색 방식과 시간 복잡도 고려).
• 비슷한 유형의 문제를 풀어본 경험이 있다면 그때 접근법을 복기해보기.

✅ 2단계: 문제 풀이 전에 접근 방법을 문장으로 정리

• "이 문제는 정렬을 활용하면 O(N log N)으로 해결할 수 있을 것 같다."
• "브루트포스로 접근하면 O(N^2)이라 시간 초과가 날 수 있다. 더 나은 방법이 있을까?"
• 손으로 간단한 예제 몇 개를 직접 시뮬레이션하며 아이디어를 정리.

✅ 3단계: 코드 작성 후 디버깅

• 테스트케이스만 통과하면 안심 금지 ❌
• "이 코드가 모든 경우를 커버할까?" 생각해보기.
• 반례를 스스로 생성해서 확인.
• 다른 사람의 풀이를 보며 비교 → 내 코드와 뭐가 다르고 더 나은 점이 무엇인지 분석.

접근 방법

이건 단순 정렬 문제. 수가 1000개까지 주어지고, 중복되지 않는다.

입력 범위가 1<= N <=1000이므로 O(N^2) 알고리즘도 사용 가능.

 

https://sober-developer.tistory.com/93

정렬 알고리즘 완전 정복 - O(N²)부터 O(N log N)까지, 정렬 알고리즘 비교

 

정렬 알고리즘 정리한 걸 기반으로 생각했을 때 입력 범위가 1 ≤ N ≤ 1,000이므로, O(N²) 정렬 알고리즘도 가능하지만 최적의 방법을 선택하는 것이 중요하다.

 

라이브러리 정렬을 사용하면 최적화된 O(N log N) 알고리즘을 활용할 수 있다.

직접 정렬 알고리즘(버블, 선택, 삽입 등)을 구현하면서 학습할 수도 있다.

 

실전에서는 라이브러리 정렬을 쓰는것이 최적이지만, 기본 정렬 알고리즘도 구현하며 학습하는 것이 좋을 것 같다.

 

코드 구현

✅ 방법 1: 라이브러리 정렬 (O(N log N), 추천)

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        Arrays.sort(arr); // O(N log N)

        for (int num : arr) {
            System.out.println(num);
        }
        sc.close();
    }
}

 

✔️ 이 방식의 장점:

• 코드가 짧고 간결함
• 내부적으로 Dual-Pivot QuickSort를 사용하여 평균 O(N log N)의 성능

---

✅ 방법 2: 버블 정렬 직접 구현 (O(N²), 학습용)

 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        // 버블 정렬 (O(N²))
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }

        for (int num : arr) {
            System.out.println(num);
        }
        sc.close();
    }
}​

✔️ 장점:

• 정렬 로직을 직접 구현하며 학습할 수 있음
• 하지만 비효율적이므로 실전에서는 사용하지 않음

---

🔍 4단계: 반례 테스트

✅ 테스트케이스를 직접 만들어서 검증

입력:  
5
5
4
3
2
1

출력:  
1
2
3
4
5

✅ 음수 포함된 경우

입력:  
5
-10
5
3
0
-1

출력:  
-10
-1
0
3
5

✅ 이미 정렬된 입력

입력:  
5
1
2
3
4
5

출력:  
1
2
3
4
5

✅ 거꾸로 정렬된 입력

 

입력:  
5
5
4
3
2
1

출력:  
1
2
3
4
5

✔️ 반례 테스트 후 확인할 것:

• 음수/0 처리되는지
• 정렬이 이미 된 상태에서 성능 문제가 없는지