프로그래머스 호텔 대실

 

첫 풀이! 일단 빨리 풀어보자라는 일념으로 해봤는데, 다행히 정답이었다.

#include <string>
#include <vector>
#include <sstream>


using namespace std;

// 00:00 ~ 23:59
// 0 ~ 1439 + 10

int map[1450];

int solution(vector<vector<string>> book_time) {
    
    
    int hour1, min1, hour2, min2;
    char dummy;
    
    int max = 0;
    
    for(auto time: book_time) {
        
        int start, end;
        
        stringstream s1(time[0]);
        s1 >> hour1 >> dummy >> min1;
        
        stringstream s2(time[1]);
        s2 >> hour2 >> dummy >> min2;
        
        start = hour1 * 60 + min1;
        end = hour2 * 60 + min2 + 9;
        
        for(int i = start; i <= end; i++) {
            map[i]++;
            
            if(map[i] > max)
                max = map[i];
        }
    }
    
    return max;
}

 

 

재풀이

#include <string>
#include <vector>
#include <sstream>


using namespace std;

// 00:00 ~ 23:59
// 0 ~ 1439 + 10

int map[1450];

int solution(vector<vector<string>> book_time) {
    
    
    int hour1, min1, hour2, min2;
    char dummy;
    
    int max = 0;
    
    for(auto time: book_time) {
        
        int start, end;
        
        stringstream s1(time[0]);
        s1 >> hour1 >> dummy >> min1;
        
        stringstream s2(time[1]);
        s2 >> hour2 >> dummy >> min2;
        
        start = hour1 * 60 + min1;
        end = hour2 * 60 + min2 + 10;
        
        map[start]++;
        map[end]--;
    }
    
    for(int i = 1; i < 1449; i++) {
        map[i] += map[i - 1];
        if(map[i] > max)
            max = map[i];
    }
    
    return max;
}

다른분의 코드를 보고, 역시나 '누적합'을 이용하면 조금 더 효율적인 퍼포먼스를 낼 수도 있겠다는 것을 깨달아서 다시 풀어보게 되었다.

대신 이 누적합의 개념을 활용하려면, 이전 코드에서 썼던 +9가 아니라 + 10으로 바꿔줘야 잘 작동한다.

 

참고

https://ksb-dev.tistory.com/269