Game Develop

[Algorithm] Programmers :: 호텔 대실 본문

Algorithm/Programmers

[Algorithm] Programmers :: 호텔 대실

MaxLevel 2023. 6. 14. 22:57

https://school.programmers.co.kr/learn/courses/30/lessons/155651

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
bool visited[1001= { false };
 
void DFS(string endTime, int index, vector<vector<string>>& book_time)
{
    int curEndTime = stoi(endTime.substr(02)) * 60 + stoi(endTime.substr(32)) + 10;
 
 
    int minEndTime = 1000000;
    int minIndex = 1000000;
 
    for (int i = index + 1; i < book_time.size(); ++i)
    {
        int nextStartTime = stoi(book_time[i][0].substr(02)) * 60 + stoi(book_time[i][0].substr(32));
        int nextEndTime = stoi(book_time[i][1].substr(02)) * 60 + stoi(book_time[i][1].substr(32));
 
        if (!visited[i] && nextStartTime >= curEndTime)
        {
            if (curEndTime < minEndTime)
            {
                minEndTime = curEndTime;
                minIndex = i;
            }
        }
    }
 
    if (minIndex == 1000000return;
 
    visited[minIndex] = true;
    DFS(book_time[minIndex][1], minIndex, book_time);
}
 
 
int solution(vector<vector<string>> book_time)
{
    int answer = 0;
 
    sort(book_time.begin(), book_time.end());
 
    for (int i = 0; i < book_time.size(); ++i)
    {
        if (!visited[i])
        {
            ++answer;
            visited[i] = true;
            DFS(book_time[i][1], i, book_time);
        }
    }
 
    return answer;
}
cs

최소한의 방만 이용해서 모든 예약을 소화하는 문제이다.

일단 시작시간을 기준으로 정렬 후, DFS로 나머지것들을 탐색하면서 현재 선택한 시작시간이 '기준시간의 종료시간+10'보다는 크면서, 종료시간이 제일 짧은것을 알아낸다음 해당 인덱스로 DFS를 진행하는 방식으로 했다.

사실 결국 나머지것들을 전부 검사하는거라서.. 시간효율은 좋지않을거라 생각했다.

실제로 통과는 했다만,효율은 좋지않았다. 통과라도 한 이유는 인풋크기가 1000밖에 안되서 그렇다.

 

이런 문제유형처럼, 공통된부분을 어떻게해야 효율적으로 알 수 있을까.. 해서 구글링하니까 누적합이라는 방법이 있다고 한다. 정말 쉽고 간단한데 효율적이다. 이제서라도 알아서 다행일 정도...

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int solution(vector<vector<string>> book_time) 
{
    int answer = 0;
 
    int arr[1451= { 0 };
    
    for (int i = 0; i < book_time.size(); ++i)
    {
        int start = stoi(book_time[i][0].substr(02)) * 60 + stoi(book_time[i][0].substr(3));
        int end = stoi(book_time[i][1].substr(02)) * 60 + stoi(book_time[i][1].substr(3)) + 10;
 
        arr[start] += 1;
        arr[end] += -1;
    }
 
    int sum = 0;
    for (int i = 0; i < 1451++i)
    {
        sum += arr[i];
        answer = max(answer, sum);
    }
 
    return answer;
}
cs

 

처음코드같은 경우 40ms도 나오기도 하는데, 누적합으로풀면 최대 0.2ms로, 압도적인 시간차이가 난다.

 

보통 기본적인 누적합의 경우, 범위의 시작부분에 +1을하고 '끝부분+1'의 부분에 -1을 하는데, 이번문제의 경우 '끝부분+1'부분이 아니라 그냥 끝부분에 -1을 체크한다.

왜냐하면 문제에서 대실이 끝난다음 10분간 청소를 한다고 한다.

대신 청소가 끝나자마자 해당 방을 이용할 수 있다.

즉, '대실 끝시간 +10'시간일 때 바로 방을 대여할 수 있다. 끝남과 동시에 바로 대여가 가능한게 문제의 조건이기 때문에 끝부분+1 에 -1을 체크하는게 아니라 그냥 끝부분에 -1을 체크해도 되는것이다.