어떤 직원의 하루 근무 시간을 담고 있는 hours 리스트가 있다고 가정해 보겠습니다. 이때 하루 근무 시간이 8시간보다 엄격하게 많으면 그날을 '피곤한 날(tiring day)'이라고 정의합니다. 또한 '성과가 좋은 구간(well-performing interval)'은 피곤한 날의 수가 피곤하지 않은 날의 수보다 엄격하게 많은 연속된 날짜 구간을 의미합니다. 우리의 목표는 이러한 성과 구간 중 가장 긴 구간의 길이를 찾는 것입니다.
예를 들어 입력이 [9, 9, 6, 0, 6, 6, 9]라면 출력은 3이 됩니다. 가장 긴 성과 구간이 [9, 9, 6]이기 때문인데, 이 구간에는 피곤한 날이 2일, 피곤하지 않은 날이 1일로 피곤한 날이 더 많기 때문입니다.
문제 해결 접근 방식
이 문제는 누적 합(prefix sum)과 해시 맵을 활용하면 O(n) 시간 복잡도로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 8시간을 초과하는 날은 +1, 그렇지 않은 날은 -1로 변환하여 누적 합(temp)을 계산합니다.
- 누적 합이 양수가 되는 순간, 처음부터 현재 위치까지가 유효한 구간이므로 답을 갱신합니다.
- 각 누적 합 값이 처음 등장한 인덱스를 해시 맵 d에 저장합니다. 같은 누적 합이 다시 나타나면 그 사이 구간의 합은 0이 되어 무의미합니다.
- 현재 누적 합에서 1을 뺀 값(temp - 1)이 맵에 존재하면, 해당 인덱스부터 현재 인덱스까지의 구간에서 피곤한 날이 더 많으므로 답을 갱신할 수 있습니다.
알고리즘 단계
- temp := 0, ans := 0으로 초기화하고, 빈 딕셔너리 d와 corner := 0을 준비합니다.
- i를 0부터 hours 배열의 크기 - 1까지 반복합니다.
- hours[i] > 8이면 temp에 1을 더하고, 아니면 1을 뺍니다.
- hours[i] > 8이면 corner = 1로 설정합니다.
- temp > 0이면 ans := max(ans, i + 1)로 갱신합니다.
- temp가 맵 d에 없으면 d[temp] := i로 저장합니다.
- temp - 1이 맵 d에 있으면 ans := max(ans, i - d[temp - 1])로 갱신합니다.
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
구현 예제
class Solution(object):
def longestWPI(self, hours):
temp = 0
ans = 0
d = {}
corner = 0
for i in range(len(hours)):
temp += 1 if hours[i]>8 else -1
if hours[i]>8:
corner = 1
if temp>0:
ans = max(ans,i+1)
if temp not in d:
d[temp]=i
if temp-1 in d:
ans = max(ans,i-d[temp-1])
return max(ans,0)
ob = Solution()
print(ob.longestWPI([9,9,6,0,6,6,9]))입력
[9,9,6,0,6,6,9]
출력
3
이 알고리즘은 배열을 한 번만 순회하면서 각 단계에서 상수 시간의 연산을 수행하므로, 전체 시간 복잡도는 O(n)이며 공간 복잡도 역시 해시 맵 저장을 위해 O(n)입니다. 단순한 이중 반복문(O(n²)) 접근법보다 훨씬 효율적이므로, 입력 배열이 클 때 특히 유용합니다.