[PS]#Lily's Homework

 

---

 

https://www.hackerrank.com/challenges/lilys-homework/problem?isFullScreen=true

Lily's Homework | HackerRank

 

#include <bits/stdc++.h> 
using namespace std; 
#define PII pair<int, int> 
int n = 0, lessResult = 0, reaterResult = 0;

int lilysHomework(vector<int> vec) 
{ 
	vector<PII> lessVec, greaterVec; 
	for (int i = 0; i < n; ++i) 
	{ 
		lessVec.push_back({ vec[i], i }); 
		greaterVec.push_back({ vec[i], i }); 
	} 
	sort(lessVec.begin(), lessVec.end()); 
	sort(greaterVec.begin(), greaterVec.end(), [](const PII& v1, const PII& v2)->bool 
		{ 
			if (v1.first > v2.first) return true; 
			return false; 
		}); 
	vector<int> calc = vec; 
	for (int i = 0; i < n; ++i) 
	{ 
		int val = lessVec[i].first, idx = lessVec[i].second; 
		if (calc[i] == val) continue; 
		auto it = lower_bound(lessVec.begin(), lessVec.end(), PII(calc[i], 0), [](const PII& v1, const PII& v2) 
			{ 
				if (v1.first < v2.first) return true; 
				return false; 
			}); 
		(*it).second = idx; 
		swap(calc[i], calc[idx]); 
		++lessResult; 
	} 
	calc = vec; 
	for (int i = 0; i < n; ++i) 
	{ 
		int val = greaterVec[i].first, idx = greaterVec[i].second; 
		if (calc[i] == val) continue; 
		auto it = lower_bound(greaterVec.begin(), greaterVec.end(), PII(calc[i], 0), [](const PII& v1, const PII& v2) 
			{ 
				if (v1.first > v2.first) return true; 
				return false; 
			}); 
		(*it).second = idx; 
		swap(calc[i], calc[idx]); 
		++reaterResult; 
	} 
	return min(lessResult, reaterResult); 
}

 

 

* 문제 풀이 과정

 

어느 위치에서나 Swap 은 가능하다고 가정할 때,

주어진 배열의 arr[i] - arr[i - 1] 이 최소임을 만족하는 배열을 만들 최솟값을 구하는 문제이다.

 

즉,

swap 을 이용해 정렬될 때까지의 최소한의 swap 호출 횟수을 말하는 것이다.

앞뒤 원소의 차가 최소가 되는 경우는 오름, 내림차순이 있기 때문에 2가지 모두 고려해야한다.

 

1. pair 로 현재 값과 인덱스를 저장해 정렬한다.

2. 정렬되야하는 배열을 만들고 이분 탐색을 이용해 해당 인덱스를 찾아 바꿔준다.

3. 오름차순, 내림차순의 2가지 경우의 최소를 구한다.