[baekjoon 22867] 종점 (스위핑, 문자열, 정렬) (C++)

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

22867번: 종점

 

버스들이 정류장에 들어오고, 나가는데 정류장에 최대 몇 대가 머무르다 가는지 출력하는 문제이다.

 

나는 처음에 시간을 모두 파싱 해서, 모두 ms로 단위를 바꿔준 다음에 누적합 풀듯이 풀었다.

시각 * 3600 * 1000 + 분 * 60 * 1000 + 초 * 1000 + 밀리초

그래서 총배열의 크기가 86400000이지만 메모리 제한이 1024mb라 통과했다.

하지만 더 간단한 방법이 있다.

 

어차피 시간 문자열도 정렬을 하면 시간 순서대로 정렬이 되기 때문에, 그냥 파싱 하지 말고 문자열 자체를 벡터에 +1, -1을 넣어준 다음에, 정렬 후 세주는 것이다.

 

배열 방법은 겹치는 시간에 모두 더해주고 나중에 누적합 풀듯이 계산하는 방법이지만 메모리 소모가 크다.

문자열 자체를 벡터에 넣어주는 방법은 동일한 시간도 벡터의 요소로 각각 있지만 정렬을 하면 결국엔 누적해서 더해지는 효과를 볼 수 있다.

 

+ 누적합처럼 나가는 시간을 x+1에 저장해주면 안 되고, 이 문제에서는 동일한 시간 일시 나가는 차가 먼저 나가고 들어오는 차가 들어오기 때문에 나가는 시각 자체에 -1을 해줘야 한다. 이 성질 때문에 문자열 자체를 저장해서 정렬해서 풀어도 되는 것 같다는 생각이 든다. 

 

1. 문자열 파싱 & 누적합 방법

#include <iostream>
#include <sstream>
#include <vector>

using namespace std;

int n, record[86400001];
int limitR, limitL = 987654321;
string from, to;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> from>>to;
		istringstream ss(from);
		string buffer = "";
		vector<string> v;
		while (getline(ss, buffer, ':')) {
			v.push_back(buffer);
		}
		istringstream ss2(to);
		while (getline(ss2, buffer, ':')) {
			v.push_back(buffer);
		}

		int l = stoi(v[0]) * 3600000 + stoi(v[1]) * 60000 + stoi(v[2].substr(0, v[2].find('.')))*1000 + stoi(v[2].substr(v[2].find('.')+1, v[2].size()));
		int r = stoi(v[3]) * 3600000 + stoi(v[4]) * 60000 + stoi(v[5].substr(0, v[5].find('.'))) * 1000 + stoi(v[5].substr(v[5].find('.') + 1, v[5].size()));
		record[l]++;
		record[r]--;
		limitR = max(limitR, r);
		limitL = min(limitL, l);
	}

	int total = 0;
	int answer = 0;
	for (int i = limitL; i <= limitR; i++) {
		total += record[i];
		answer = max(answer, total);
	}
	cout << answer;
}

 

2. 문자열 정렬

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
string from, to;
typedef pair<string, int> psi;
vector<psi> v;

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> from >> to;
		v.push_back({ from, 1 });
		v.push_back({ to, -1 });
	}
	sort(v.begin(), v.end());

	int result = 0;
	int answer = 0;
	for (auto k : v) {
		result += k.second;
		answer = max(answer, result);
	}
	cout << answer;

}