Baekjoon 23968 알고리즘 수업 - 버블 정렬 1 JAVA

23968번: 알고리즘 수업 - 버블 정렬 1

문제

오늘도 서준이는 버블 정렬 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

N개의 서로 다른 양의 정수가 저장된 배열 A가 있다. 버블 정렬로 배열 A를 오름차순 정렬할 경우 K 번째 교환되는 수를 구해서 우리 서준이를 도와주자.

크기가 N인 배열에 대한 버블 정렬 의사 코드는 다음과 같다.

bubble_sort(A[1..N]) { # A[1..N]을 오름차순 정렬한다.
    for last <- N downto 2
        for i <- 1 to last - 1
            if (A[i] > A[i + 1]) then A[i] <-> A[i + 1]  # 원소 교환
}

 

입력

첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 10,000), 교환 횟수 K(1 ≤ K ≤ N2)가 주어진다.

다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109)

출력

K 번째 교환되는 두 개의 수를 작은 수부터 한 줄에 출력한다. 교환 횟수가 K 보다 작으면 -1을 출력한다.

풀이

실제로 K 번째에 교환되는 값을 출력해야하기에, 주어지는 버블 정렬 의사 코드를 이용하여 버블정렬을 구현한다.

구현을 하면서 원소 교환이 일어나는 지점에서 cnt 변수를 증가시키면서 교환 횟수를 증가해간다.

 

이때 경우의 수를 두가지로 생각할 수 있다.

 

첫 번째는 교환이 일어나며 K번째 교환되는 값이 나오는 지점이 존재하는 경우

두 번째는 K번째보다 작게 교환이 일어나서 -1을 출력하는 경우가 있다

 

첫 번째의 경우 교환지점에서 cnt를 체크하며 K와 같은 경우에 return하여

bubble_sort 마지막에 "-1"로 초기화 하는 코드라인을 타지 않으면 각 정렬과정들이 ans에 저장되며 그 문자열을 출력한다.

 

두 번째의 경우 마지막까지 return으로 반복문을 탈출하지 못했다면 K보다 작게 반복한것이기에

ans = "-1"으로 만드는 코드가 실행되기에 -1을 출력한다.

코드

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

public class Main {
	static int n, k;
	static String ans="";
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n=Integer.parseInt(st.nextToken());
		k=Integer.parseInt(st.nextToken());
		int [] a = new int[n+1];
		st = new StringTokenizer(br.readLine());
		for(int i=1;i<=n;i++)
			a[i]=Integer.parseInt(st.nextToken());
		bubble_sort(a);
		
		System.out.println(ans);
	}
	public static void bubble_sort(int [] a) {
		int cnt=0;
		for(int last=n;last>=2;last--) {
			for(int i=1;i<=last-1;i++)
				if(a[i]>a[i+1]) {
					int temp=a[i];
					a[i]=a[i+1];
					a[i+1]=temp;
					cnt++;
					if(cnt==k) {
						ans=a[i]+" "+a[i+1];
						return;
					}
				}
		}
		ans="-1";
	}
}