[백준 13334번 C/C++] 철로

 

[백준 13334번 C/C++] 철로

 

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

13334번: 철로

---

 

해결전략

 

정렬

set, multiset

우선순위 큐 priority_queue

 

※ 주의할 점

이 문제에서 set을 사용할거면 multiset을 사용해야 한다.

• set은 중복된 원소를 허용하지 않는다. 반면 첫 번째 코드에서는 multiset을 허용한다.
• multiset을 사용하여 시작점이 같은 데이터도 모두 저장해야 한다. 이렇게 하면 시작점이 같은 모든 데이터를 고려하여 최대 개수를 찾을 수 있다.

---

 

 

처음 시도한 코드 - 잘못된 접근 + 시간초과

 

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

struct Data {
	int start; int end; int dist;

	Data(int a, int b, int c) {
		start = a;
		end = b;
		dist = c;
	}

	bool operator<(const Data& oper) const {
		if (start == oper.start)
			return end < oper.end;

		return start < oper.start;
	}
};

int n, d;
vector<Data> v;
int minP, maxP;
int answer;

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

	cin >> n;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;

		if (a <= b) { 
			minP = min(minP, a);
			maxP = max(maxP, b);
			v.push_back({ a, b, b - a }); 
		}
		else {
			minP = min(minP, b);
			maxP = max(maxP, a);
			v.push_back({ b, a, a - b });
		}
	}
	cin >> d;
	sort(v.begin(), v.end());

	//for (int i = 0; i < n; i++) {
	//	cout << v[i].start << " " << v[i].end << " " << v[i].dist << "\n";
	//}

	for (int i = minP; i <= maxP; i++) {
		
		int cnt = 0;
		for(int j = 0; j < n; j++){
			if (i <= v[j].start && v[j].end <= i + d) {
				cnt++;
			}
			else if (i > v[j].start) {
				break;
			}
		}

		answer = max(answer, cnt);
	}

	cout << answer;

	return 0;
}

---

 

정답코드 - multiset 사용

 

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

struct Data {
	int start; int end; int dist;

	Data(int a, int b, int c) {
		start = a;
		end = b;
		dist = c;
	}
	// 끝점이 같으면 시작점이 작은 것이 먼저 오게 하고, 그렇지 않으면 끝점이 작은 것이 먼저 오게 한다.
	bool operator<(const Data& oper) const {
		if (end == oper.end)
			return start < oper.start;

		return end < oper.end;
	}
};

int n, d; // n: 데이터의 개수, d: 거리의 최대값.
vector<Data> v;
int answer;

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

	cin >> n;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;

		if (a <= b) v.push_back({ a, b, b - a });
		else v.push_back({ b, a, a - b });
	}
	cin >> d;
	sort(v.begin(), v.end());

	multiset<int> mySet;

	for (int i = 0; i < n; i++)
	{
		if (v[i].end - d <= v[i].start){
			mySet.insert(v[i].start);
		}

		// multiset에서 끝점에서 거리의 최대값을 뺀 값보다 크거나 같은 첫 번째 요소를 찾을 때까지 multiset의 첫 번째 요소를 삭제한다.
		set<int>::iterator iter;
		for (iter = mySet.begin(); iter != mySet.end(); iter = mySet.begin())
		{
			if (v[i].end - d <= *iter) break;

			mySet.erase(mySet.begin());
		}

		int cnt = mySet.size(); // multiset의 크기는 조건을 만족하는 데이터의 개수
		answer = max(answer, cnt);
	}


	cout << answer;

	return 0;
}

 

 

※ 주의할 점. 실수한 부분

정답 코드 - iterator를 사용한 요소 삭제

	set<int>::iterator iter;
    for (iter = mySet.begin(); iter != mySet.end(); iter = mySet.begin())
    {
        if (v[i].end - d <= *iter) break;

        mySet.erase(mySet.begin());
    }

 

잘못된 코드 - range-based for loop에서 요소 삭제

    for (auto iter : mySet)
    {
        if (v[i].end - d <= iter) break;

        mySet.erase(iter);
    }

 

첫 번째 코드와 두 번째 코드의 차이점은 multiset에서 요소를 삭제하는 부분

첫 번째 코드에서는 multiset에서 요소를 삭제할 때 반복자(iterator)를 사용한다. 반복자를 사용하면 삭제 작업 이후에도 반복자가 유효하게 유지된다. 

반면에, 두 번째 코드에서는 range-based for loop를 사용하여 multiset에서 요소를 삭제하고 있습니다. 이 경우, loop 변수 'iter'는 const 참조이므로 multiset의 요소를 가리키는 데 사용되는 내부 반복자가 삭제되면 무효화됩니다. 이로 인해 런타임 에러가 발생하거나 예상하지 못한 결과를 얻게 됩니다.

multiset이나 set 등에서 요소를 삭제할 때는 반복자를 사용하는 것이 안전하다. range-based for loop를 사용할 경우에는 요소를 삭제하지 않아야 한다.

---

 

 

정답코드 - priority_queue 사용

 

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

struct Data {
	int start; int end; int dist;

	Data(int a, int b, int c) {
		start = a;
		end = b;
		dist = c;
	}
	// 끝점이 같으면 시작점이 작은 것이 먼저 오게 하고, 그렇지 않으면 끝점이 작은 것이 먼저 오게 한다.
	bool operator<(const Data& oper) const {
		if (end == oper.end)
			return start < oper.start;

		return end < oper.end;
	}
};

int n, d; // n: 데이터의 개수, d: 거리의 최대값.
vector<Data> v;
int answer;

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

	cin >> n;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;

		if (a <= b) v.push_back({ a, b, b - a });
		else v.push_back({ b, a, a - b });
	}
	cin >> d;
	sort(v.begin(), v.end());


	priority_queue<int> pQ;

	for (int i = 0; i < n; i++) 
	{
		int start = v[i].start;
		int end = v[i].end;

		if (end - start > d) continue; // 시작점과 끝점의 거리가 최대 거리보다 크면 고려할 필요없음

		// 우선순위 큐에 시작점을 넣음. 내림차순으로 정렬될 수 있도록 -를 붙여줌
        // priority_queue는 기본 오름차순 정렬임. 오름차순 정렬을 변경하지 않고 내림차순으로 사용하기 위해 start의 값에 -부호를 붙여 넣어주어 원하는 순서로 정렬함
		pQ.push(-start); 
        
		while (!pQ.empty()) 
		{
			// 큐의 top에 있는 값(가장 작은 값)과 최대 거리의 합이 끝점보다 크거나 같으면 break. 해당 경우는 범위 내 들어간다는 의미
			if (-pQ.top() + d >= end) break;

			pQ.pop(); // d 범위 내에 들어가지 않으면 pop
		}

		answer = max(answer, (int)pQ.size());
	}


	cout << answer;

	return 0;
}