[코딩테스트] 백준 2750 자바

백준 2750

백준 2750 문제

import java.util.*;

public class Boj2750 {

    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();
        }

        for (int i = 0; i < n - 1; i++) { // 현재 인덱스의 수와 다음 인덱스의 수를 비교하기 때문에 마지막 인덱스까지 갈 필요가 없어 n-1
            int swap = 0; // swap 횟수
            for (int j = 0; j < n - 1 - i; j++) { // 맨 뒤의 인덱스는 오름차순으로 정렬된 수이기에 n-1-i로 반복할 범위를 줄인다.
                if (arr[j] > arr[j + 1]) { // 앞의 수가 뒤의 수보다 크면 스왑해준다.
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swap++;
                }
            }
            if (swap == 0) break; // 스왑 횟수가 0이면 모두 정렬된 것이기 때문에 루프를 멈춘다.
        }

        for (int i : arr) { // 정렬된 배열 출력
            System.out.println(i);
        }
    }
}

풀이

1. 해당 문제는 n의 길이가 최대 1000이며, 제한 시간이 2초로 시간 복잡도가 O(n2)인 알고리즘을 사용하여도 충분히 넉넉한 문제이다.
2. 시간 복잡도가 O(n2)인 버블 정렬을 사용해보았다.
3. Scanner를 통해 입력될 수의 개수를 n으로 받는다.
4. n만큼의 길이를 가진 배열을 만든다.
5. n만큼 반복하며 배열에 입력되는 수를 담는다.
6. 버블 정렬은 인접한 두 수를 비교하면서 가장 큰 수가 마지막부터 차례대로 루프당 한 번씩 정렬되기 떄문에 이중 반복문을 사용해야 한다.
7. n-1번째 루프를 돌 때 정렬이 완료되기 때문에 바깥쪽 루프는 n-1만큼만 반복한다.
8. 마지막부터 루프당 한 번씩 정렬되기 때문에 때문에 n-1-i만큼 반복한다.
9. 앞의 수가 뒤의 수보다 클 경우에 두 수를 바꿔준다.
10. 만약 한 번의 루프동안 스왑 횟수가 0번이라면 모두 정렬이 된 것이기 때문에 루프를 중지한다.