이 문제에서는 날짜의 DD-MM-YYYY(일-월-연도) 형식을 나타내는 3개의 정수로 구성된 두 개의 배열 date1[]과 date2[]가 주어집니다. 우리의 과제는 두 날짜 사이의 일 수를 구하는 것입니다.
예시를 통해 문제를 이해해 보겠습니다.
입력
date1[] = {13, 3, 2021}, date2[] = {24, 5, 2023}출력
802
설명
두 날짜의 차이는 2년, 2개월(3월 → 5월), 그리고 11일입니다.
2*365 + (30 + 31) + 11 = 802
해결 접근 방법
가장 단순한 해결 방법은 시작 날짜 date1부터 date2까지 하루씩 반복하면서 일 수를 세는 것입니다. 이 방법도 동작하지만, 더 효율적인 방법이 존재합니다.
효율적인 접근 방법
더 효율적인 방법은 각 날짜 date1[]과 date2[]까지의 총 일 수를 각각 계산한 뒤, 두 값의 절대 차이를 구하는 것입니다. 이렇게 하면 반복문 없이 한 번의 연산으로 결과를 얻을 수 있습니다.
여기서 기준점은 0000년 1월 1일부터 해당 날짜까지의 일 수를 계산합니다. 총 일 수는 다음 세 가지 요소의 합으로 구성됩니다.
1. 연도(YEAR)
해당 연도 date1[2]의 첫날까지의 일 수입니다.
일 수 = 365 * (연도) + 윤년의 개수
2. 월(MONTH)
해당 월의 첫날까지의 일 수로, 미리 정의된 누적 일수 배열에서 가져옵니다.
일 수 = monthDays[date[1]]
monthDays 배열은 각 월의 첫날까지 누적된 총 일 수를 저장하고 있습니다.
3. 일(DATE)
해당 월에서 경과한 일 수 자체입니다.
이 세 가지 값을 모두 더하면 특정 날짜까지의 총 일 수가 됩니다. 두 날짜에 대해 각각 계산한 값의 차이가 곧 최종 결과입니다.
솔루션의 동작을 보여주는 프로그램입니다.
예제 코드
#include <iostream>
#include <math.h>
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)
years--;
return ( (years / 4) - (years / 100) + (years / 400) );
}
// 두 날짜 사이의 일 수를 계산하는 함수
int countNoOfDays(int date1[], int date2[]){
long int dayCount1 = (date1[2] * 365);
dayCount1 += monthDays[date1[1]];
dayCount1 += date1[0];
dayCount1 += countLeapYearDays(date1);
long int dayCount2 = (date2[2] * 365);
dayCount2 += monthDays[date2[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<<"두 날짜 사이의 일 수는 "<<countNoOfDays(date1, date2);
return 0;
}출력
두 날짜 사이의 일 수는 802
코드 설명
위 코드에서 countLeapYearDays() 함수는 그레고리력 규칙에 따라 윤년의 개수를 계산합니다. 즉, 4로 나누어 떨어지는 해는 윤년이지만, 100으로 나누어 떨어지는 해는 평년이며, 다시 400으로 나누어 떨어지는 해는 윤년입니다. 또한 1월이나 2월인 경우에는 해당 연도의 윤일(2월 29일)이 아직 지나지 않았으므로 연도에서 1을 빼고 계산합니다.
이 알고리즘의 시간 복잡도는 O(1)로, 날짜 차이가 아무리 크더라도 상수 시간 안에 결과를 얻을 수 있다는 것이 가장 큰 장점입니다.