[백준 10818번/JAVA] 배열의 최댓값 최솟값 출력 | Bubble Sort 시간 초과

문제

Bubble Sort 사용의 문제점

import java.util.*;

public class Main {
    public static void main(String[] args){
        //N값을 받고
        //N개의 정수를 입력받아 배열에 저장
        //배열 정렬 (버블정렬)
        //인덱스 0, N으로 최솟값, 최댓값 출력
        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++) {
            for(int j=0; j<N-i-1; j++) {
                //앞이 더 크면 둘의 자리 교환
                if(arr[j]>arr[j+1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                }
            }
        }
        System.out.print(arr[0] + " " + arr[N-1]);
    }
}

맨 처음 떠올린 아이디어는 정렬 후 index 0, N-1을 꺼내는 방법이다.

정렬 중 가장 구현이 간단하고 직관적인 Bubble Sort를 사용했는데 시간초과가 발생했다.

 

백준 1~3단계 문제에서는 딱히 시간복잡도를 고려하지 않아도 쉽게 문제가 통과되었지만, 중첩 for문이 포함된 코드는 연산 횟수가 N^2이 되기 때문에 위험하다.

 

이제부터는 제한 시간, 연산 횟수를 모두 고려하여 알고리즘을 설계할 필요가 있다.

아래 포스팅에 간단히 시간복잡도에 대해 정리해두었다.

 

https://oigie.tistory.com/6

• Bubble Sort의 시간복잡도
  • 인접한 index 둘을 비교하여 서로 자리를 교환한다.
  • 1회전 수행할 때마다 가장 큰 원소가 맨 뒤에서부터 차례로 위치하게 되므로, 비교대상에서 하나씩 제외시킨다.
  • 시간복잡도는 (n-1) + (n-2) + (n-3) + ... + 1 = O(n^2)
  • 정렬 여부와 상관없이 항상 모든 비교를 진행하므로 best, average, worst case 모두 O(n^2)의 시간복잡도를 가진다. (굉장히 비효율적)
• Bubble Sort의 연산 횟수
  • 문제에서 주어진 정수의 갯수: 1 <= N <= 1,000,000
  • Bubble Sort 시간복잡도: O(N^2)
  • 연산 횟수(big-O): 1억
  • 연산 횟수가 1억보다 작아야 함. 시간초과 발생
• 그렇다면 개선 방법은?
  • 배열의 원소 정렬에서 최악의 경우 시간복잡도는 N^2이다. >> 정렬을 사용하더라도 시간복잡도가 낮은 것을 썼어야 했다. 그런데 이 문제는 정렬을 쓰지 않아도 충분히 구현할 수 있다. (원소값 바로 비교하기)
  • Scanner을 Buffer로 대체하면 실행시간을 단축할 수 있다.

Scanner + 정렬O

이 문제를 Arrays.sort()로 많이 풀길래 한 번 사용해봤다.
Arrays.sort()는 배열의 원소를 오름차순으로 정렬해주는 java.util 내의 클래스이다.
java 유틸리티에서 지원해주는 기능이므로 구현이 굉장히 간단하다.

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

        System.out.print(arr[0] + " " + arr[N-1]);
    }
}

통과는 됐지만 정렬과정이 있어 시간이 굉장히 오래 걸린다.
Arrays.sort()는 시간복잡도가 최악의 경우 O(N^2)라고 한다.

Scanner + 정렬X

정렬을 사용하지 않고 임의의 값과 배열의 원소를 하나씩 비교해서 min, max를 찾는다.

import java.util.*;

public class Main {
    public static void main(String[] args){
        //min, max값을 지정(index 0)
        //min, max와 arr[i]를 하나씩 비교하며 min, max를 update

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

        int min = arr[0];
        int max = arr[0];
        for(int i=0; i<N; i++) {
            if(min>arr[i])
                min = arr[i];
            if(max<arr[i])
                max = arr[i];
        }
        System.out.print(min + " " + max);
    }
}

역시나 통과는 됐지만 여전히 시간이 오래 걸린다.

정렬을 사용하지 않고 바로 비교하는 경우 시간복잡도는 O(N)이다.

Buffer + 정렬X

시간복잡도를 줄이기 위해 Scanner가 아닌 Buffer을 사용해보자.

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

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

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());

        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int min = arr[0];
        int max = arr[N-1];
        for(int i=0; i<N; i++) {
            if(min>arr[i])
                min = arr[i];
            if(max<arr[i])
                max = arr[i];
        }
        bw.write(min + " " + max);
        bw.close();    
    }
}

Scanner에 비해 실행시간이 확연히 빨라졌다.

정리

• 정렬은 시간복잡도 측면에서 좋지 않다. 최악의 경우 O(N^2)이다.
• 정렬을 사용하지 않고 min, max를 찾는 방법은 방법은 배열 원소를 임의의 값과 바로 비교하는 것이다.
• 시간복잡도를 줄이기 위해 Scanner 대신 Buffer를 써보자.

+) 배열을 사용하지 않고 min, max값을 주어진 범위의 경계값으로 설정하여 바로 비교하는 방법으로 푼 경우도 있었는데, 메모리 측면에서 좋은 방법인 것 같다.