https://www.hackerrank.com/challenges/lilys-homework/problem?isFullScreen=true
#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 |