[백준/Java] 1377번 버블 소트 프로그램 1

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

// 버블 정렬 응용
public class Main {
	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		// 숫자의 개수 N 입력받기
		int N = Integer.parseInt(st.nextToken());

		// 배열
		myData[] A = new myData[N];
		
		// 배열에 N개의 수 입력받기
		for(int i=0; i<N; i++) 
		{
			st = new StringTokenizer(br.readLine());
			A[i] = new myData(Integer.parseInt(st.nextToken()), i);
		}
		
		// 오름차순으로 정렬하기, O(logn)의 시간복잡도
		Arrays.sort(A);
		
		int max = 0;
		for(int i=0; i<N; i++)
		{
			// 정렬전 index - 정렬 후 index
			int difference = A[i].index - i;
			
			// difference 의 최댓값 저장하기
			if (max < difference) 
			{
				max = difference;
			}
		}
		System.out.println(max+1);
		br.close();
	}
}

// 값과 인덱스를 가지는 myData 클래스
class myData implements Comparable<myData>
{
	int value;
	int index;
	
	public myData(int value, int index)
	{
		super();
		this.value = value;
		this.index = index;
	}
	

	// value 기준 오름차순 정렬하기
	@Override
	public int compareTo(myData o)
	{
		return this.value - o.value;
	}
}

/*
 * [Comparable] docs.oracle.com/javase/8/docs/api/java/lang/Comparable.html#method.summary
 * Comparable 인터페이스에는 
 * compareTo 메소드 하나가 선언되어있다.
 * Comparable을 사용하고자 한다면 
 * compareTo 메소드를 재정의(Override/구현)를 해줘야 한다. 
 */

/* 
 * 추가
 * https://st-lab.tistory.com/243
 * Comparable과 Comparator의 차이?
 * 
 * Comparable은 "자기 자신과 매개변수 객체를 비교"한다.
 * Comparator는 "두 매개변수 객체를 비교"한다.
 */

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

1377번: 버블 소트

 

버블 정렬의 swap이 한 번도 일어나지 않은 루프가

언제인지 알아내는 문제입니다.

 

'버블 정렬의 이중 for 문에서

안쪽 for 문 전체를 돌 때

swap이 일어나지 않았다'는 것은

이미 모든 데이터가 정렬됐다는 것을 의미합니다.

 

이때는 프로세스를 바로 종료해

시간 복잡도를 줄일 수 있습니다.

 

하지만 이 문제는 N의 최대 범위가 500,000이므로

버블 정렬로 문제를 풀면

시간이 초과될 수 있습니다.

 

안쪽 for 문이 몇 번 수행됐는지 구하는

다른 아이디어가 필요합니다.

 

 

 

 

---

 

코드 그대로 쓰면 시간초과..

package Test;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

// 버블 정렬
public class Main {
	// Java 언어에서는 call by reference가 지원되지 않아 
	// swap 함수를 구현하기는 사실상 불가합니다. 
	// 다만, 배열이나 리스트 같은 
	// 컨테이너 객체 내부의 원소 값들을 교환하는 것은 가능합니다.
	public static void swap(int[] array, int index1, int index2)
	{
		int temp = array[index1];
		array[index1] = array[index2];
		array[index2] = temp;
	}
	
	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		// 숫자의 개수 N 입력받기
		int N = Integer.parseInt(st.nextToken());

		// 배열
		int[] A = new int[N+1];
		
		// 배열에 N개의 수 입력받기
		for(int i=1; i<=N; i++) 
		{
			st = new StringTokenizer(br.readLine());
			A[i] = Integer.parseInt(st.nextToken());
		}
		
		// 오름차순으로 정렬하기
		// Arrays.sort(A);
		
	
		
		// 버블 정렬
		boolean changed = false;
		for (int i=1; i<=N+1; i++) 
		{
		    changed = false;
		    for (int k=1; k<=N-i; k++) 
		    {
		        if (A[k] > A[k+1]) {
		            changed = true;
		            swap(A, k, k+1);
		        }
		    }
		    if (changed == false) {
		        System.out.println(i);
		        break;
		    }
		}
		
		// 정렬된 배열 출력하기
//		for(int i=1; i<N+1; i++) 
//		{
//			System.out.print(A[i] + " ");
//		}
		br.close();
		
		
	}
	

}