백준 1377번(버블 소트)[JAVA]

풀이

문제의 C++코드를 보면, 버블 정렬에서의 2중 for문 중, 안쪽 for문이 돌아갔는데도 정렬을 하지 않았을 경우, break한다. 즉,정렬이 다 되어있을 경우에, for문을 끝까지 돌지 않고 중간에 탈출한다는 것이다. 그리고 이를 몇번쨰 인덱스에서 탈출했는지를 출력한다. 문제에서 주어진 n이 500,000이기 때문에, 똑같이 버블정렬을 통해 찾으면 버블 정렬의 시간 복잡도는 O(n^2)이기 때문에 시간초과가 날 것이다.
핵심 알고리즘
이 문제의 핵심은 바로, 버블 정렬의 이해에 있다. 버블 정렬의 안쪽 for문에서 각 원소는 움직이지 않거나 1칸씩 움직인다.
이러한 점을 활용해서, 어떠한 정렬을 활용하더라도 기존의 인덱스와 정렬 후 인덱스가 가장 많이 차이나는 값+1(+1을 하는 이유는, 주어진 문제의 버블 정렬에서는 for문이 일단 돌아가야 정렬이 되어있는지 안되어있는지를 확인할 수 있기 때문이다)을 구하면 된다.

ex) 4 2 3 1 5 6 7 8 9 인 배열에서의 버블 정렬을 상상해보자.
4 2 3 1 부분의 정렬이 완성되면, 그 이후는 for문이 돌아가긴 하지만 이미 정렬된 부분이라 각각의 원소들이 움직이지 않을 것이다.
즉, 1이 왼쪽으로 3번오면 이 정렬은 끝난다. 그렇기에 이 3번을 카운트하고, 다시 5부터 다시 정렬을 시작하면 문제에서의 changed가 false가 유지되므로, +1을 해주는 것이다.

팁
Scanner를 쓰면 시간초과가 아니라, 메모리 초과가 된다…
Scanner는 시간 복잡도 뿐만 아니라 공간 복잡도에서도 별로인 것이다!!
그냥 처음부터 BufferedReader와 StringTokenizer(이 문제에서는 필요 없지만)를 쓰면 되지만, scanner의 직관적인 코드가 좋아서 계속 쓰고 있다.

소스 코드

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

public class 버블소트 {
	public static void main(String[] args) throws Exception {
		//Scanner sc = new Scanner(System.in);
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		Node[] arr = new Node[n];
		
		for (int i = 0; i < n; i++) {
			arr[i] = new Node(Integer.parseInt(br.readLine()), i);
		}
		
		Arrays.sort(arr);
		int max = 0;
		for (int i = 0; i < n; i++) {
			if (max < arr[i].idx - i) {
				max = arr[i].idx-i;
			}
		}
		System.out.println(max+1);
	}
	
	static class Node implements Comparable<Node> {
		int value;
		int idx;
		
		public Node(int value, int idx) {
			super();
			this.value = value;
			this.idx = idx;
		}
		
		@Override
		public int compareTo(Node o) {
			// TODO Auto-generated method stub
			return this.value - o.value;
		}
	}
}

태클 감사합니다.
조언 환영입니다.