[백준] 2750 -자바

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

 

매우 간단한 문제다.

Arrays.sort() 한 번으로도 풀 수 있는 문제이나 버블정렬에 대한 구현을 직접 해볼 수 있는 문제라 풀어보는게 좋다.

버블정렬은 O(N^2)의 시간 복잡도를 가지고 있다.

이 문제의 제한시간은 1. 그러나 주어진 N의 최대 수는 1000이다. 따라서 최악의 경우 1000*1000=1,000,000. 백만번의 연산이 발생한다. 1초당 1억번의 연산이 걸린다고 일반적으로 잡으니 이 문제는 O(N^2)의 시간 복잡도여도 문제가 되지 않는다.

---

처음 풀었던 풀이이다. 이 문제도 정답이나 한가지 빠트린게 있으니 두번째 풀이도 보길 바란다.

public class Main {
    public static void main(String[] args) throws IOException {
        /*
        1.수의 개수를 받는다. n개의 수를 배열로 받는다
        2.for(int i=0; i<n; i++){
        if(arr[i]>arr[i+1){
            arr[i]와 arr[i+1]의 자리를 바꿔준다. =>버블정렬 1회차로 한자리수만 확정
        3.이걸 n개 만큼 반복
         */
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        for(int i =0; i<n; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }

        for(int i=0; i<n-1; i++) {
            for (int j = 0; j < n - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int var = 0;
                    var = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = var;
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int a: arr){
            sb.append(a).append('\n');
        }
        System.out.println(sb);
    }
}

---

위 풀이와 차이점은 이중for문에서 내부 for문의 범위다.

기존에 n-1번까지 돌던걸 n-1-i번까지 도는 것에 차이가 있다.

오름차순으로 버블정렬을 한 번 돌리면 맨 마지막자리는 확정이 된다. 그러므로 다음번 반복에서는 이미 확정된 자리까지 비교할 필요가 없으므로 n-1-i가 되는 것이다. 

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

public class Main {
    public static void main(String[] args) throws IOException {
        /*
        1.수의 개수를 받는다. n개의 수를 배열로 받는다
        2.for(int i=0; i<n; i++){
        if(arr[i]>arr[i+1){
            arr[i]와 arr[i+1]의 자리를 바꿔준다. =>버블정렬 1회차로 한자리수만 확정
        3.이걸 n개 만큼 반복. 반복할 때 끝까지 반복할 필요없다. 반복 한 번 돌때마다 확정된 자리수들이 생기니 그때는 반복하지 않아도된다.
         */
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        for(int i =0; i<n; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }

        for(int i=0; i<n-1; i++) {
            for (int j=0; j < n-1-i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int var = 0;
                    var = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = var;
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int a: arr){
            sb.append(a).append('\n');
        }
        System.out.println(sb);
    }
}