Baekjoon 23899 알고리즘 수업 - 선택 정렬 5 JAVA

23899번: 알고리즘 수업 - 선택 정렬 5

문제

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

N개의 서로 다른 양의 정수가 저장된 배열 A가 있다. 선택 정렬로 배열 A를 오름차순 정렬할 경우 정렬 과정에서 배열 A가 배열 B와 같은 경우가 발생하는지 확인해 보자. 초기 상태 배열 A도 정렬 과정에서 발생 가능한 경우로 생각하자.

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

selection_sort(A[1..N]) { # A[1..N]을 오름차순 정렬한다.
    for last <- N downto 2 {
        A[1..last]중 가장 큰 수 A[i]를 찾는다
        if (last != i) then A[last] <-> A[i]  # last와 i가 서로 다르면 A[last]와 A[i]를 교환
    }
}

 

입력

첫째 줄에 배열 A, B의 크기 N(5 ≤ N ≤ 10,000)이 주어진다.

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

다음 줄에 서로 다른 배열 B의 원소 B1, B2, ..., BN이 주어진다. (1 ≤ Bi ≤ 109)

출력

선택 정렬로 배열 A를 오름차순 정렬하는 과정에서 배열 A가 배열 B와 같은 경우가 발생하면 1, 아니면 0을 출력한다.

풀이

1. 배열 A와 B를 입력받으면서 cnt를 체크해서 처음 입력받는 배열이 동일한지 체크한다.

2. 주어지는 의사코드를 이용하여 함수를 구현해준다.

3. 구현된 함수를 이용하며 정렬을 하면서 각 단계마다 정렬되는 A와 B를 비교하며 배열의 길이만큼 값이 동일하다면 두 배열은 같다

 

코드

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

public class Main {
	static int n;
	static int [] a, b;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n=Integer.parseInt(br.readLine());
		a = new int [n+1];
		b=new int[n+1];
		int cnt=0;
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=1;i<=n;i++)
			a[i]=Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		for(int i=1;i<=n;i++) {
			b[i]=Integer.parseInt(st.nextToken());
			if(b[i]==a[i])
				cnt++;
		}
		if(cnt==n)
			System.out.println(1);
		else
			System.out.println(selection_sort()?"1":"0");
	}
	
	public static boolean selection_sort() {
		int i;
		for(int last=n;last>=2;last--) {
			int max=0, maxi=0;
			for(i=1;i<=last;i++) {
				if(max<a[i]) {
					max=a[i];
					maxi=i;
				}
			}
			if(last!=maxi) {
				int temp=a[last];
				a[last]=a[maxi];
				a[maxi]=temp;
			}
			int cnt=0;
			for(i=1;i<=n;i++)
				if(a[i]==b[i])
					cnt++;
				else
					break;
			if(cnt==n)
				return true;
		}
		return false;
	}
}