백준 2594번 [놀이공원](C++)-yes6686- 티스토리

백준 문제 풀이: 2594 [놀이공원]

---

문제 링크: https://www.acmicpc.net/problem/2594

문제 설명:

놀이공원 운영 시간이 10:00부터 22:00까지 주어졌을 때, 놀이공원에서 빈 시간이 가장 긴 구간(손님이 없는 시간)을 찾는 프로그램을 작성하세요. 놀이기구 간의 공백은 10분, 그리고 두 놀이기구가 서로 다른 시간에 운영되는 경우에는 추가적인 공백 시간 20분을 고려해야 합니다.

입력 조건:

• 첫 줄에 놀이기구 개수 N이 주어집니다. (1 ≤ N ≤ 1000)
• 둘째 줄부터 N개의 줄에 각 놀이기구의 시작 시간과 종료 시간이 24시간 표기로 주어집니다. (1000 ≤ 시작 시간 ≤ 종료 시간 ≤ 2200)

출력 조건:

• 놀이공원이 운영 중 손님이 없는 가장 긴 시간(분 단위)을 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 놀이기구 일정 저장 구조체
struct Schedule {
    int start, end;
};

// 시간 차이 계산 함수
int timeDiff(int h1, int m1, int h2, int m2) {
    return (h2 * 60 + m2) - (h1 * 60 + m1);
}

int main() {
    int n;
    cin >> n;
    vector<Schedule> schedules(n);

    // 놀이기구 일정 입력받기
    for (int i = 0; i < n; i++) {
        cin >> schedules[i].start >> schedules[i].end;
    }

    // 시작 시간을 기준으로 정렬
    sort(schedules.begin(), schedules.end(), [](Schedule a, Schedule b) {
        return a.start < b.start;
    });

    int maxGap = 0; // 최대 빈 시간
    int currentHour = 10, currentMinute = 0; // 운영 시작 시간

    // 모든 일정 순회하며 빈 시간 계산
    for (const auto& schedule : schedules) {
        int startHour = schedule.start / 100;
        int startMinute = schedule.start % 100;

        // 현재 시간과 놀이기구 시작 시간의 차이를 계산
        int gap = timeDiff(currentHour, currentMinute, startHour, startMinute) - 10;
        if (gap > 0) {
            maxGap = max(maxGap, gap);
        }

        // 놀이기구 종료 시간 업데이트
        int endHour = schedule.end / 100;
        int endMinute = schedule.end % 100;
        if (timeDiff(currentHour, currentMinute, endHour, endMinute) > 0) {
            currentHour = endHour;
            currentMinute = endMinute;
        }
    }

    // 마지막 놀이기구 이후의 빈 시간 계산
    int closingGap = timeDiff(currentHour, currentMinute, 22, 0) - 10;
    if (closingGap > 0) {
        maxGap = max(maxGap, closingGap);
    }

    // 결과 출력
    cout << maxGap << endl;

    return 0;
}

---

코드 설명

위 코드는 놀이공원의 모든 놀이기구 일정 사이의 빈 시간을 계산하고 가장 긴 구간을 출력합니다.

• 정렬: 놀이기구 시작 시간을 기준으로 정렬하여 일정 간 비교를 간단히 처리합니다.
• 시간 차이 계산: `timeDiff` 함수를 사용하여 두 시간 사이의 차이를 분 단위로 계산합니다.
• 공백 계산: 현재 시간과 다음 놀이기구 시작 시간 사이의 빈 시간을 계산하며, 10분을 제외합니다. 이후 종료 시간을 업데이트하여 다음 공백 계산에 반영합니다.
• 마지막 공백 처리: 마지막 놀이기구 이후 놀이공원 운영 종료 시간(22:00)까지의 빈 시간을 추가로 계산합니다.

시간 복잡도 분석:

• 정렬: O(N log N).
• 빈 시간 계산: O(N).

따라서 전체 시간 복잡도는 O(N log N)입니다.

---

결과

다음은 입력 예시와 출력 결과입니다:

입력:
3
1000 1030
1040 1100
1600 1630

출력:
290

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!