알고리즘/HackerRank_문제풀이

[PS]#Lily's Homework

코딩하는상후니 2022. 11. 20. 10:47

 


 

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

Lily's Homework | HackerRank

Help George figure out Lily's homework

www.hackerrank.com

 

#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가지 경우의 최소를 구한다.

 

 

 

 

'알고리즘 > HackerRank_문제풀이' 카테고리의 다른 글

[PS]#Roads and Libraries  (0) 2022.12.03
[PS]#The Story of a Tree  (0) 2022.11.23
[PS]#Bear and Steady Gene  (0) 2022.11.20
[PS]#Ice Cream Parlor  (0) 2022.11.20
[PS]#Gridland Metro  (0) 2022.11.17