원제: Count Days Spent Together
| 플랫폼 | 문제 번호 | 난이도 | 언어 |
|---|---|---|---|
| 리트코드 | 2409 | 쉬움 (Easy) | Python 3 |
Alice와 Bob이 각각 로마에 도착한 날부터 떠나는 날까지 머무르며, 양 끝 날짜도 포함합니다. 두 사람이 동시에 머무는 날짜의 총수를 반환합니다.
날짜는 모두 같은 윤년이 아닌 해의 유효한 날짜이며, 형식은 5자 문자열 MM-DD입니다. 각 사람의 도착 날짜는 떠나는 날짜보다 빠르거나 같습니다. 월별 일수는 [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]입니다.
예제 1: arriveAlice = "08-15", leaveAlice = "08-18", arriveBob = "08-16", leaveBob = "08-19" → 3. 겹치는 날짜는 8월 16일부터 18일까지입니다.
예제 2: arriveAlice = "10-01", leaveAlice = "10-31", arriveBob = "11-01", leaveBob = "12-31" → 0. 두 구간은 겹치지 않습니다.
원문의 예제 1은 두 구간의 겹치는 날짜가 3일임을 보여 주고, 예제 2는 겹치는 날이 없을 때 0을 반환함을 보여 줍니다.
월과 일을 그대로 비교하는 대신, 각 날짜를 1월 1일부터 몇 번째 날인지 나타내는 정수로 변환합니다. 두 사람이 모두 머무는 구간의 시작은 도착일 중 더 늦은 날이고, 끝은 떠나는 날 중 더 이른 날입니다. 따라서 start = max(aa, ab), end = min(la, lb)로 교집합 후보를 얻습니다. 시작이 끝보다 뒤라면 겹치는 날이 없으므로 0을 반환하고, 그렇지 않으면 양 끝을 포함해 end - start + 1일입니다.
제출 코드의 days(txt)는 txt[:2]에서 월, txt[3:]에서 일을 정수로 읽습니다. sum(months[:month-1]) + day는 해당 월 앞까지의 일수에 현재 날짜의 일을 더하므로, 날짜를 연중 일수로 바꿉니다. 같은 달 안에서도 날짜 순서가 일수의 대소 관계와 일치하고, 월이 달라도 앞선 달의 일수가 누적되므로 구간의 최댓값·최솟값으로 겹침을 판별할 수 있습니다.
코드 추적: 예제 1에서 aa = 227, ab = 228, la = 230, lb = 231입니다. 따라서 start = 228, end = 230이고, max(0, end - start + 1)은 3입니다. 예제 2에서는 start가 305, end가 304이므로 max(0, 0)을 반환합니다. max(0, ...)가 겹침이 없는 경우의 음수 길이를 0으로 처리하며, + 1은 시작일과 끝일을 모두 세기 위해 필요합니다.
class Solution:
def countDaysTogether(self, arriveAlice: str, leaveAlice: str, arriveBob: str, leaveBob: str) -> int:
months = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
def days(txt):
month = int(txt[:2])
day = int(txt[3:])
return sum(months[:month-1]) + day
aa = days(arriveAlice)
ab = days(arriveBob)
la = days(leaveAlice)
lb = days(leaveBob)
start = max(aa,ab)
end = min(la,lb)
return max(0, end - start + 1)
days는 최대 11개의 월별 일수를 더하고, 나머지 연산은 상수 횟수만 수행합니다. 월의 개수를 12로 고정하면 시간 복잡도는 O(1), 보조 공간은 O(1)입니다. 반환값은 정수 하나이므로 결과 저장 공간도 O(1)입니다.
체류 구간은 양 끝 날짜를 포함합니다. 날짜를 연중 일수로 바꾸는 과정은 윤년이 아닌 해의 월별 일수 목록에 의존합니다. 이 문제의 입력은 유효한 날짜이므로 별도의 날짜 검증은 하지 않습니다.