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

2021. 7. 15. 22:28· Koala - 4기

 

힌트 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;
}
저작자표시 (새창열림)

'Koala - 4기' 카테고리의 다른 글

[BOJ] 21774 가희와 로그 파일  (0) 2021.07.16
[BOJ 21774] - 가희와 로그 파일  (2) 2021.07.16
[BOJ] 11060 점프 점프  (2) 2021.07.15
[BOJ] 11060번 점프점프  (2) 2021.07.15
[BOJ 11060] : 점프 점프  (1) 2021.07.15
'Koala - 4기' 카테고리의 다른 글
  • [BOJ] 21774 가희와 로그 파일
  • [BOJ 21774] - 가희와 로그 파일
  • [BOJ] 11060 점프 점프
  • [BOJ] 11060번 점프점프
KauKoala
KauKoala
항공대 알고리즘 동아리 Koala 🥰
Koala항공대 알고리즘 동아리 Koala 🥰
KauKoala
Koala
KauKoala
전체
오늘
어제
  • 분류 전체보기 (1883)
    • 공지 게시판 (10)
    • 정보 게시판 (8)
    • Codeforce (15)
    • acm-icpc (6)
    • Koala - 1기 (16)
    • Koala - 2기 (111)
      • Programming Contest (1)
      • A반 (20)
      • B반 (39)
      • C반 (22)
      • 기초 강의 (18)
    • Koala - 3기 (10)
      • 기초 스터디 (7)
    • Koala - 4기 (67)
    • Koala - 5기 (144)
      • 기초 알고리즘 스터디 (75)
      • 코딩테스트 준비 스터디 (68)
    • Koala - 6기 (102)
      • 기초 알고리즘 스터디 (75)
      • 코딩테스트 준비 스터디 (25)
      • 모의 테스트 스터디 (1)
    • Koala - 7기 (167)
      • 기초 알고리즘 스터디 (97)
      • 코딩테스트 준비 스터디 (68)
      • 모의 테스트 스터디 (1)
    • Koala - 8기 (44)
      • 기초 알고리즘 스터디 (32)
      • 코딩테스트 준비 스터디 (10)
      • 코드포스 버츄얼 스터디 (0)
      • 프로그래머스 LV2 스터디 (0)
    • Koala - 9기 (205)
      • 기초 알고리즘 스터디 (138)
      • 코딩테스트 준비 스터디 (64)
      • 모의테스트 준비 스터디 (1)
    • Koala - 10기 (117)
      • 기초 알고리즘 스터디 (30)
      • 코딩테스트 준비 스터디 (86)
      • 모의테스트 준비 스터디 (1)
    • Koala - 11기 (151)
      • 기초 알고리즘 스터디 (46)
      • 코딩테스트 준비 스터디 (104)
      • 모의테스트 준비 스터디 (1)
    • Koala - 12기 (86)
      • 기초 알고리즘 스터디 (31)
      • 코딩테스트 준비 스터디 (55)
    • Koala - 13기 (119)
      • 기초 알고리즘 스터디 (52)
      • 코딩테스트 준비 스터디 (67)
    • Koala - 14기 (116)
      • 기초 알고리즘 스터디 (39)
      • 코딩테스트 준비 스터디 (77)
    • Koala - 15기 (138)
      • 기초 알고리즘 스터디 (73)
      • 코딩테스트 준비 스터디 (65)
    • Koala - 16기 (47)
      • 코딩테스트 기초 스터디 (16)
      • 코딩테스트 심화 스터디 (31)
    • Koala - 17기 (62)
      • 코딩테스트 기초 스터디 (15)
      • 코딩테스트 심화 스터디 (47)
    • Koala - 18기 (31)
      • 코딩테스트 기초 스터디 (11)
      • 코딩테스트 심화 스터디 (20)
    • Koala - 19기 (38)
      • 코딩테스트 기초 스터디 (7)
      • 코딩테스트 심화 스터디 (31)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

  • 🐨항공대 알고리즘 학회 Koala 3기 모집
  • 🐨항공대 알고리즘 학회 Koala 2기 모집
  • 소모임 소개

인기 글

태그

  • 파이썬
  • dfs
  • C++
  • BOJ
  • BFS
  • dp
  • 백트래킹
  • 백준

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.3.0
KauKoala
백준 21774번 가희와 로그 파일 풀이
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.