백준 24052: 알고리즘 수업-삽입 정렬2

[ 문제위치 ]

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

24052번: 알고리즘 수업 - 삽입 정렬 2

 

[ 문제풀이 ]

삽입 정렬을 이용하여 배열을 정렬하는 것을 기본으로 하는 문제이다.

 

삽입 정렬 알고리즘에 관해서는 아래 링크로

https://unlock546.tistory.com/3

삽입 정렬

이를 활용한 1번 문제 풀이는 아래 링크에서 확인할 수 있다.

https://unlock546.tistory.com/4

백준 24051: 알고리즘 수업-삽입 정렬1

 

위의 내용을 보고 왔다면 K 번의 저장이 일어난 조건이 같으므로 해당 숫자 대신 배열 전체를 출력해주는 반복문을 설정해주면 된다.

 

#include <iostream>
#include <queue>
using namespace std;

#define MAX 100000

int main() {
	int N, K;
	int A[MAX];
	cin >> N >> K;

	int cnt = 0;//저장 횟수 카운트 용 변수

	for (int i = 0; i < N; i++) {//입력
		cin >> A[i];
	}

	for (int i = 1; i < N; i++) {//삽입 정렬 알고리즘
		int key = A[i];
		int j = i - 1;

		while (-1 < j && A[j] > key) {
			A[j + 1] = A[j];
			cnt++;//카운트하고 조건 충족하면 출력 후 종료
			if (cnt == K) {
				for (int x = 0; x < N; x++) {//정렬 출력
					cout << A[x] << " ";
				}
				return 0;
			}
			j--;
		}

		if (A[j + 1] != key) {//제자리에서 정렬이 끝나 저장 안 되는 경우 제외
			cnt++;
			A[j + 1] = key;
		}

		if (cnt == K) {
			for (int x = 0; x < N; x++) {//정렬 출력
				cout << A[x] << " ";
			}
			return 0;
		}

	}
	cout << -1;//위 조건에서 충족되지 않으면 cnt < K 이므로 -1 출력
}