백준 23882 알고리즘 레슨 – 정렬 선택 2 JAVA

문제

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의 크기 N(5 ≤ N ≤ 10,000)과 교환 횟수 K(1 ≤ K ≤ N)를 제공합니다.

다른 배열 A의 요소 A1, A2, …, AN은 다음 줄에 지정됩니다.
(1 ≤ AI ≤ 10^9)

누르다

라인에서 K 교환이 발생한 직후 배열 A를 반환합니다.
교환 횟수가 K보다 작으면 -1을 반환합니다.

설명

2023.03.26 – (알고리즘/백준) – 백준 23881 알고리즘 클래스 – 선택정렬 1 JAVA

위의 문제와 마찬가지로 교환 횟수를 세는 것이 문제입니다.

그러나 유일한 차이점은 만족스러운 교환의 수를 찾으면 현재 상태가 부여된다는 것입니다.

암호

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

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());
		StringBuilder sb = new StringBuilder();
		int n=Integer.parseInt(st.nextToken()), k=Integer.parseInt(st.nextToken()), cnt=0;
		int () A = new int(n);
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<n;i++)
			A(i)=Integer.parseInt(st.nextToken());
		
		for(int i=n-1;i>=0;i--) {
			int max=0, idx=0;
			for(int j=0;j<i;j++) {
				if(max<A(j)) {
					max=A(j);
					idx=j;
				}
			}
			if(A(i)<A(idx)) {
				int temp = A(i);
				A(i)=A(idx);
				A(idx)=temp;
				cnt++;
			}			
			if(cnt==k)
				break;
		}
		if(cnt<k)
			System.out.println(-1);
		else {
			for(int i=0;i<n;i++)
				sb.append(A(i)+" ");
			System.out.println(sb.toString());
		}
	}
}