[Baekjoon/C++] 23883번 - 알고리즘 수업 - 선택 정렬 3

[백준] Baekjoon Online Judge

문제로 이동

 

문제

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

N개의 서로 다른 양의 정수가 저장된 배열 A가 있다. 선택 정렬로 배열 A를 오름차순 정렬할 경우 K 번째 교환되는 수를 구하자.

N이 매우 커서 시간 초과를 고민하고 있는 우리 서준이를 도와주자.

크기가 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의 크기 N(5 ≤ N ≤ 500,000), 교환 횟수 K(1 ≤ K ≤ N)가 주어진다.

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

 

출력

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

 

---

예제 입력	예제 출력
5 2 3 1 2 5 4	2 3
5 4 3 1 2 5 4	-1

---

풀이

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

int selection_sort(int N, int K);

map <int, int> m;
int A[500001];

// 선택 정렬 
int selection_sort(int N, int K) {
	int count = 0; // 교환 횟수
	int idx = N - 1;

	map <int, int>::reverse_iterator it = m.rbegin();

	for (it = m.rbegin(); it != m.rend(); ++it) {
		int big = it->second; // A[]중 가장 큰 수

		// last와 big이 서로 다르면 교환이 발생한다.
		if (big != idx) {
			int tmp = A[idx];
			A[idx] = it->first;
			A[big] = tmp;

			// 각 숫자의 현재 인덱스 위치
			it->second = idx;
			map<int, int>::iterator find = m.find(tmp);
			find->second = big;

			count++;
		}

		// K 번째 교환
		if (count == K) {
			printf("%d %d\n", A[big], A[idx]); // 출력

			return 0;
		}

		idx--;
	}

	// 출력
	printf("-1\n");

	return 0;
}

int main() {
	int N, K; //  배열 A의 크기 N, 교환 횟수 K
	scanf("%d %d", &N, &K);

	for (int i = 0; i < N; i++) {
		scanf("%d", &A[i]);
		m.insert(map<int, int>::value_type(A[i], i));
	}

	selection_sort(N, K);

	return 0;
}

이번 문제에서 주어지는 N의 범위는 매우 크다. 그렇기에 시간 초과가 발생할 수 있는데, 이를 줄이기 위해 맵을 사용했다. 맵에는 숫자와 해당 숫자가 입력된 숫자가 저장되도록 했다. 

 

// 선택 정렬 
int selection_sort(int N, int K) {
	int count = 0; // 교환 횟수
	int idx = N - 1;

	map <int, int>::reverse_iterator it = m.rbegin();

	for (it = m.rbegin(); it != m.rend(); ++it) {
		int big = it->second; // A[]중 가장 큰 수

		// last와 big이 서로 다르면 교환이 발생한다.
		if (big != idx) {
			int tmp = A[idx];
			A[idx] = it->first;
			A[big] = tmp;

			// 각 숫자의 현재 인덱스 위치
			it->second = idx;
			map<int, int>::iterator find = m.find(tmp);
			find->second = big;

			count++;
		}

		// K 번째 교환
		if (count == K) {
			printf("%d %d\n", A[big], A[idx]); // 출력

			return 0;
		}

		idx--;
	}

	// 출력
	printf("-1\n");

	return 0;
}

맵은 원소를 오름차순으로 정렬해서 저장한다. 해당 맵에 저장한 숫자들은 큰 수부터 차근차근 필요하기 때문에 맵을 뒤에서부터 순서대로 읽어 big에 저장했다. 여기서 선택정렬을 위해 가장 큰 수를 찾기 위해 A[]를 모두 뒤져보는 과정이 사라져 시간을 아낄 수 있게 된다. idx는 가장 큰 수가 위치해야하는 인덱스이다.

만약 big이 idx와 같지 않다면 해당 숫자는 교환이 발생해야 하는 수이므로 A[]의 교환이 발생한다. A[]의 교환이 끝나면 m의 second를 A[]의 교환에 맞게 바꿔준다. 이 과정이 끝나면 count를 1 증가시켰다.

그러다 count가 K와 같아지면 K 번째 교환되는 두 개의 수를 출력하고, 0을 return해서 함수를 끝냈다.

만약 for문이 모두 돌았는데도 count가 K와 같은 경우가 한 번도 없다면 -1을 출력하고 함수를 끝내도록 했다.

 

<참고>

https://www.hanbit.co.kr/channel/category/category_view.html?cms_code=CMS9990721111