백준 21774번 가희와 로그 파일 풀이

 

힌트 1

약 21년의 시간을 초 단위로 나타내어 대소 비교를 할 수 있습니다.

 

힌트 2

로그에 대한 시간들이 순서대로 정렬되어 있을 때, 어떤 시간 A보다 크거나 같은 수가 처음 발견되는 위치는 O(logn) 시간에 찾을 수 있습니다.

 

힌트 3

종료 시각보다 큰 수가 처음 발견되는 위치 - 시작 시각보다 크거나 같은 수가 처음 발견되는 위치

 

번외 힌트

사실 문제처럼 연, 월, 일, 시, 분, 초로 되어있는 로그는 숫자만 모두 모아두면 그 자체로 대소비교가 가능합니다.

예를 들어 2000-01-02 12:12:12 -> 20000102121212 , 2021-04-05 17:17:11 -> 20210405171711

이 부분은 long long 형으로 변환해도 되지만, 그냥 string 그대로 정렬하는 것이 좋습니다.

저도 방금 알아낸 방법인데 이 방법이 훨씬 편한 것 같네요!

 

풀이 1

로그를 long long 형으로 변환 과정을 거친 후 푼 풀이입니다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

vector<ll>loge[7]; //loge[i] : lv i 이상인 로그 목록
int calc[] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };

ll strTolong(string date, string time) {
	ll sum = 0;

	int year, month, day, hour, minute, sec;

	//stoi : string to int 변환 함수입니다.
	year = stoi(date.substr(0, 4));
	month = stoi(date.substr(5, 2));
	day = stoi(date.substr(8, 2));

	hour = stoi(time.substr(0, 2));
	minute = stoi(time.substr(3, 2));
	sec = stoi(time.substr(6, 2));

	ll tmp = 1;
	sum += sec * tmp;
	tmp = 60;
	sum += minute * tmp;
	tmp = 3600;
	sum += hour * tmp;

	tmp *= 24;
	sum += (day - 1) * tmp;

	int tmp_day = 0;
	for (int i = 1; i < month; i++) {
		if (i == 2 && year % 4 == 0) tmp_day += 29;
		else {
			tmp_day += calc[i];
		}
	}

	sum += tmp_day * tmp;

	tmp_day = 0;
	for (int i = 2000; i < year; i++) {
		if (i % 4 == 0) tmp_day += 366;
		else tmp_day += 365;
	}

	sum += tmp_day * tmp;

	return sum;

}
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, q;
	cin >> n >> q;

	for (int i = 0; i < n; i++) {
		string date, t;
		cin >> date >> t;
		//string.substr(idx, cnt) : idx 부터 cnt 만큼 문자열을 잘라 리턴합니다.
		string time = t.substr(0, 8);
		int num = t[t.size() - 1] - '0';

		ll sum = strTolong(date, time);

		//loge[i] 를 i 이상 로그로 선언했기 때문에 그 이상을 모두 push해줍시다.
		for (int i = 1; i <= num; i++) loge[i].push_back(sum);
	}

	//이분 탐색 전 미리 정렬해줍니다.
	for (int i = 1; i <= 6; i++) {
		sort(loge[i].begin(), loge[i].end());
	}

	for (int i = 0; i < q; i++) {
		ll start = 0, end = 0;

		string a, b, c;
		cin >> a >> b >> c;

		string start_date, start_time, end_date, end_time;
		start_date = a;
		start_time = b.substr(0, 8);
		end_date = b.substr(9, 10);
		end_time = c.substr(0, 8);
		int num = c[c.size() - 1] - '0';

		start = strTolong(start_date, start_time);
		end = strTolong(end_date, end_time);

		//end보다 큰 수가 처음 등장하는 인덱스 - start보다 크거나 같은 수가 처음 등장하는 인덱스
		//로 처리하면 바로 정답이 나오게됩니다. 만약 end보다 큰 수가 없다면 배열 크기가 리턴됩니다.
		int up_idx = upper_bound(loge[num].begin(), loge[num].end(), end) - loge[num].begin();
		int down_idx = lower_bound(loge[num].begin(), loge[num].end(), start) - loge[num].begin();

		cout << up_idx - down_idx << "\n";
	}

	return 0;
}

 

풀이 2

문자열 그대로 넣어서 푼 코드입니다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

vector<string>loge[7]; //loge[i] : lv i 이상인 로그 목록

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, q;
	cin >> n >> q;

	for (int i = 0; i < n; i++) {
		string date, t;
		cin >> date >> t;
		
		string time = "";
		
		for (int j = 0; j < date.size(); j++) {
			if (date[j] != '-') time += date[j];
		}
		for (int j = 0; j < t.size() - 2; j++) {
			if (t[j] != ':') time += t[j];
		}

		int num = t[t.size() - 1] - '0';


		for (int i = 1; i <= num; i++) loge[i].push_back(time);
	}

	for (int i = 1; i <= 6; i++) {
		sort(loge[i].begin(), loge[i].end());
	}

	for (int i = 0; i < q; i++) {

		string a, b, c;
		cin >> a >> b >> c;

		string start = "", end = "";

		for (int j = 0; j < a.size(); j++) {
			if (a[j] != '-') start += a[j];
		}

		for (int j = 0; j < b.size(); j++) {
			if (b[j] == '#') break;
			if (b[j] != ':') start += b[j];
		}
		
		for (int j = 9; j < b.size(); j++) {
			if (b[j] != '-') end += b[j];
		}

		for (int j = 0; j < c.size() - 2; j++) {
			if (c[j] != ':') end += c[j];
		}

		int num = c[c.size() - 1] - '0';

		int up_idx = upper_bound(loge[num].begin(), loge[num].end(), end) - loge[num].begin();
		int down_idx = lower_bound(loge[num].begin(), loge[num].end(), start) - loge[num].begin();

		cout << up_idx - down_idx << "\n";
	}

	return 0;
}