기록을

https://www.welcomekakao.com/learn/courses/30/lessons/42748

벡터에 담긴 수를 잘라서 정렬 이후에, 주어진 index의 데이터를 벡터에 담아서 반환하면 되는 문제이다.

문제에서는 index의 시작을 1로 보고 있다는 것만 주의하면 되는 문제이다.

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

vector<int> solution(vector<int> array, vector<vector<int>> commands) {
	vector<int> answer;

	for (int i = 0; i < commands.size(); i++) {
		vector<int> temp;
		for (int j = commands[i][0]-1; j <= commands[i][1]-1; j++) {
			temp.push_back(array[j]);
		}
		sort(temp.begin(), temp.end());
		answer.push_back(temp[commands[i][2] - 1]);
		temp.clear();
	}
	return answer;
}

문제 설명

-n명의 선수들의 실력이 입력으로 주어진다.

-실력차이가 k이하인 선수들은 같은 버스에 타고 있을 수 없다.

-이 때 필요한 버스의 수는?

풀이

처음에는 벡터에 pair을 담는 형태로 선수 정보와 버스 정보를 담으려고 했다.

이 방식으로 하면 새로운 선수에 대한 처리를 할 때마다, 이전의 선수들에 대한 정보를 모두 검사해야 한다.

하지만 n < 200,000이기 때문에 O(N) 못해도 O(nlogn)에는 해결하겠다는 생각으로 접근해야 할 것이다.

기본 아이디어는 선수들의 실력을 오름차순으로 정렬하는 것이다.

정렬된 배열 1 3 4 5 7 9 를 선수 정보라고 치고, k = 3이라고 한다면

3은 1과 같은 버스에 탈 수 없다. (3 - 1 < k ) 3까지 확인한 결과로 버스는 두대가 필요하다.

4를 확인할 때, 이미 두대가 필요한 것을 알고 있으므로 두칸 앞으로가서 1부터 비교한다. 1과도 같은 버스에 탈 수 없기 때문에 버스는 한대가 더 추가된다. 1과도 같이 탈 수 없으면, 정렬된 상태이기 때문에 1보다 더 큰 실력을 가진 사람과는 비교할 필요도 없는 것이다.

5를 확인할 때 이미 세대가 필요하다는 것을 알고있으므로 세칸 앞으로 가서 1부터 확인한다. 1과 5는 같은 버스에 탈 수 있다.

이런식으로 진행해주면 된다.

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

int arr[200001];
int main(void) {

	int tc;
	cin >> tc;
	for (int t = 1; t <= tc; t++) {

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

		sort(arr, arr + n); //오름차순 정렬
		
		int bus = 1;

		for (int i = 1; i < n; i++) {
			if (arr[i] - arr[i - bus] <= k)
				bus++;
		}
		cout << "Case #" << t << '\n' << bus << '\n';
	}
	return 0;
}