[G4] 백준 23884번 알고리즘 수업 - 선택 정렬 4 C++ 트리를 사용한 집합과 맵, map

리뷰

 

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

풀긴 풀었는데 공간 및 시간 복잡도가 썩 맘에 드는 풀이 방법은 아닌듯 하다.

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 배열의 원소 개수를 저장할 변수
• k : 최대 교환 횟수를 저장할 변수
• arr : 배열의 초기 정보를 저장할 배열
• dic : 값/인덱스 매핑을 위한 map

 

함수

없음

 

 

문제풀이

1. n, k값을 입력 받고, n개의 원소를 입력 받아 arr, dic초기화를 진행한다.
2. n-1에서 0으로 진해앟는 for문을 개행한다.
3. 변수 key, value에 dic의 맨 마지막 요소의 값을 파싱하고, 변수 cur에 arr[i]의 값을 저장한다.
4. 만약 key와 cur이 다르다면 swap함수를 통해 arr[i]와 arr[value]를 바꾸어준다.
5. dic[cur]의 값을 value로 변경하고, k를 감소시킨다. 만약 감소시킨 후 k값이 0이라면 break처리한다.
6. dic에서 맨 마지막 요소를 erase처리한다.
7. for문이 종료된 후 k의 값이 남아있다면 -1을, 아니라면 arr의 요소를 공백을 기준으로 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. for문을 돌때 현재 값은 정확히 i번째로 큰 수가 들어와야 하므로 dic에선 항상 최대값만 순회해주었다.
2. swap여부와 상관 없이 현재 사용한 최대값은 for문 루프 종료 시점에 dic에서 제거해주었다.
3. 원소의 값 범위는 (1 ≤ Ai ≤ 10^9)이므로 값/인덱스 변환이 필요하다.

 

정답 코드

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

const int N = 5e5;
int n, k;
int arr[N];
map<int, int> dic;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> k;
	for (int i = 0; i < n; ++i) {
		int d; cin >> d;
		arr[i] = d;
		dic[d] = i;
	}

	for (int i = n - 1; i >= 0; --i) {
		auto [key, value] = *dic.rbegin();
		int cur = arr[i];

		//cout << key << " " << value << " " << cur << " " << k << "\n";
		if (key != cur) {
			swap(arr[i], arr[value]);
			dic[cur] = value;
			if (!--k) break;
		}

		dic.erase(--dic.end());
	}
	
	if (k) cout << -1;
	else for (int i = 0; i < n; ++i) cout << arr[i] << " ";
}