문제 소개
n개의 항공편이 있으며, 각 항공편에는 1부터 n까지 번호가 붙어 있다고 가정해 보겠습니다. 항공편 예약 목록이 주어졌을 때, i번째 예약은 bookings[i] = [i, j, k] 형태로 표현되며, 이는 i번 항공편부터 j번 항공편까지(양 끝 포함) k개의 좌석을 예약했다는 의미입니다.
목표는 길이가 n인 배열 answer를 만들어, 각 항공편에 예약된 좌석 수를 항공편 번호 순서대로 나타내는 것입니다. 예를 들어 입력이 [[1,2,10],[2,3,20],[2,5,25]]이고 n = 5라면, 출력은 [10, 55, 45, 25, 25]가 됩니다.
효율적인 접근 방법: 차분 배열(Difference Array)
각 예약마다 해당 범위의 모든 항공편에 좌석 수를 하나씩 더하는 단순한 방식도 가능하지만, 이 경우 시간 복잡도가 O(n × m)까지 커질 수 있습니다(m은 예약의 개수). 대신 차분 배열 기법을 활용하면 O(n + m) 시간 안에 문제를 해결할 수 있습니다.
핵심 아이디어는 간단합니다. 각 예약 구간 [i, j]에 대해 시작 지점에 k를 더하고, 구간이 끝난 바로 다음 지점에서 k를 뺍니다. 그런 다음 배열 전체에 대해 누적 합(prefix sum)을 한 번만 계산하면, 모든 항공편의 최종 예약 좌석 수를 자연스럽게 얻을 수 있습니다.
구체적인 풀이 단계는 다음과 같습니다.
- 크기가 n인 배열 res를 만들고 모든 값을 0으로 초기화합니다.
- bookings의 각 항목 i에 대해 다음을 수행합니다.
- res[i[0] - 1]에 i[2]를 더합니다. (시작 항공편에 좌석 수 반영)
- i[1] < n이라면 res[i[1]]에서 i[2]를 뺍니다. (구간 종료 지점 표시)
- 인덱스 1부터 n-1까지 순회하며 res[i] = res[i] + res[i-1]로 누적 합을 계산합니다.
- res를 반환합니다.
예제 동작 과정 살펴보기
입력 [[1,2,10],[2,3,20],[2,5,25]], n = 5를 기준으로 단계별로 확인해 보겠습니다.
- 예약 [1,2,10]: 1~2번 항공편에 10석 → 인덱스 0에 +10, 인덱스 2에 -10
- 예약 [2,3,20]: 2~3번 항공편에 20석 → 인덱스 1에 +20, 인덱스 3에 -20
- 예약 [2,5,25]: 2~5번 항공편에 25석 → 인덱스 1에 +25 (j = n이므로 감산 생략)
이 상태에서 누적 합을 계산하면 [10, 55, 45, 25, 25]라는 최종 결과를 얻게 됩니다.
구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
class Solution(object):
def corpFlightBookings(self, bookings, n):
res = [0 for i in range(n)]
for i in bookings:
res[i[0]-1]+=i[2]
if(i[1]<n):
res[i[1]]-=i[2]
for i in range(1,n):
res[i]+=res[i-1]
return res
ob = Solution()
print(ob.corpFlightBookings([[1,2,10],[2,3,20],[2,5,25]],5))입력
[[1,2,10],[2,3,20],[2,5,25]] 5
출력
[10, 55, 45, 25, 25]
마무리
차분 배열 기법은 구간에 값들을 일괄 더하거나 빼야 하는 다양한 문제에서 활용할 수 있는 강력한 도구입니다. 이 문제처럼 예약·갱신 요청이 많고 구간 연산이 반복되는 상황에서 시간 복잡도를 크게 줄여 주므로, 코딩 테스트와 실무 모두에서 꼭 익혀 두면 유용합니다.