[LeetCode] 1109. Corporate Flight Bookings

[문제 링크]

https://leetcode.com/problems/corporate-flight-bookings/description/

 

[문제]

주어진 flight bookings 배열은 여러 회사의 비행기 예약 정보를 포함하고 있습니다. 각 예약은 다음과 같은 3개의 값을 갖는 튜플로 제공됩니다:

first : 예약이 시작되는 공항
last : 예약이 종료되는 공항
num : 예약된 좌석 수

여러 예약 정보가 주어졌을 때, 각 공항에 대한 비행기 좌석 예약의 합을 구하는 문제입니다.

[풀이 과정]

누적합을 사용하는 문제였습니다.
end + 1에 - seats를 적용한다는 것만 이해하면 쉬운 문제입니다.

 

왜 start는 seats값을 그냥 저장하고 end에는 아무것도 저장하지 않고 end + 1에 - seats를 하나면
start ~ end까지는 결국 나중에 누적합 결과를 도출할 때 값이 채워지지만 end + 1에 - seats를 하지 않으면
end + 1 에도 전에 seats 값이 영향을 주기 때문에 - seats를 미리 저장해 놓는 것입니다.

 

[코드]

class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        Map<Integer, Integer> memo = new HashMap<>();
        int[] answer = new int[n];

        for(int i = 0; i < bookings.length; i++) {
            int start = bookings[i][0];
            int end = bookings[i][1];
            int seats = bookings[i][2];

            memo.put(start, memo.getOrDefault(start, 0) + seats);
            memo.put(end+1, memo.getOrDefault(end+1, 0) - seats);
        }

        for(int i = 1; i <= n; i++) {
            int value = memo.getOrDefault(i,0);
            if(i == 1) {
                answer[i-1] = value;
            } else {
                answer[i-1] = answer[i-2] + value;
            }
        }

        return answer;
    }
}

[회고]

누적합 알고리즘을 응용해 볼 수 있어 좋았습니다.

 

 

 

 

질문과 피드백은 언제나 환영입니다.

감사합니다.