ภาพรวมปัญหา
ได้รับวันที่สองวันในรูปแบบ DD-MM-YYYY (เก็บในอาร์เรย์ขนาด 3) ต้องหาจำนวนวันระหว่างสองวันนั้น
ตัวอย่าง
อินพุต
date1[] = {13, 3, 2021}, date2[] = {24, 5, 2023}
เอาต์พุต
802
คำอธิบาย
ความต่าง: 2 ปี, 2 เดือน, 11 วัน 2×365 + (30+31) + 11 = 802
วิธีแก้ปัญหา
วิธีที่ 1: วนลูปนับวัน - O(จำนวนวัน) ช้า
วิธีที่ 2: คำนวณจำนวนวันสะสมจากวันที่ 1/1/0000 - O(1) ⭐
คำนวณจำนวนวันทั้งหมดจนถึงแต่ละวันที่ แล้วหาความต่าง
สูตร:
Total Days = year × 365 + leap_years + month_days[month] + day
โดย leap_years = year/4 - year/100 + year/400 (ปรับถ้าเดือน ≤ 2)
โค้ดตัวอย่าง
#include <iostream>
#include <cmath>
using namespace std;
const int monthDays[12] = { 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365 };
int countLeapYearDays(int d[]) {
int years = d[2];
if (d[1] <= 2) // ก่อนเดือนมีนาคม ไม่รวม leap day ของปีนั้น
years--;
return (years / 4) - (years / 100) + (years / 400);
}
int countNoOfDays(int date1[], int date2[]) {
long int dayCount1 = (long)date1[2] * 365;
dayCount1 += monthDays[date1[1] - 1]; // monthDays index 0-based
dayCount1 += date1[0];
dayCount1 += countLeapYearDays(date1);
long int dayCount2 = (long)date2[2] * 365;
dayCount2 += monthDays[date2[1] - 1];
dayCount2 += date2[0];
dayCount2 += countLeapYearDays(date2);
return abs(dayCount1 - dayCount2);
}
int main() {
int date1[3] = {13, 3, 2021};
int date2[3] = {24, 5, 2023};
cout << "The number of days between two dates is " << countNoOfDays(date1, date2);
return 0;
}
เอาต์พุต
The number of days between two dates is 802
สรุป
วิธีนี้ O(1) เร็วกว่าการวนลูปมาก จัดการ leap year ถูกต้องด้วยกฎ กระโดดปีทุก 4 ปี ยกเว้นปีหาร 100 ลงตัว แต่หาร 400 ลงตัวก็เป็น leap year
