Programmers - 추석 트래픽

---

title: Programmers - 추석 트래픽
date: 2022-08-13
tags:

• Algorithm

---

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

문제 요약

처리가 완료된 시각, 그리고 해당 처리의 처리 시간이 주어진다. 처리 시간은 0.001~3s 사이이다.
1초간(시작 및 완료 시각 포함) 최대 처리량을 return한다.

문제 풀이

이런식으로 시작과 끝이 명확하게 주어지고 임의의 구간의 최대값을 구하는 문제는 보통 정렬 후 처리하면 풀리는 문제가 많다.
이 문제 또한 동일하게 처리 시작 시각과 완료 시각을 구한 후, 시작 혹은 완료 시각을 기준으로 정렬하여 최대값을 구하면 된다.


주어진 문자열을 이용하여 처리 시작 시각과 완료 시각을 구한 후, 이를 vector에 넣어 완료 시각 기준으로 정렬한다.
매 완료 시각마다 확인한다. 완료 시각 기준 앞은 확인할 필요가 없다.
이전에 완료한 것이 있다면 이미 확인이 끝났으며, 완료한 것이 없다면 처리 도중이기에 현재 완료 기준 뒤를 확인할 때 count가 된다.
완료 시각 기준 정렬이기에 뒤에 오는 것들의 시작 시각은 무작위이며, 완료 시각과 동시에 처리중일 수도 있으며, 처리가 시작되지 않았을 수도 있다.
뒤에 오는 것들을 모두 조회하며 현재 완료 시각 + 0.999s 까지 시작하였다면 count한다.
1초의 처리량이지만 시작 및 완료 시각이 포함이므로, 현재 완료 시각이 3.543s 라면 4.542s까지가 1초간 처리한 것을 확인하는 범위이다.


실제 서비스에서 유저의 이용량이 골고루 분포되어 있을 수도 있으나, 특정 시간에 많이 이용할 가능성이 높다.
유저의 이용량을 확인하여야 리소스가 부족하거나 많을 경우 조정할 수 있다.
이 알고리즘의 경우 O(n^2)이며, 일일 처리량이 1억건이라면 너무 많은 loop가 시행된다.
유저의 이용량을 실시간으로 확인한다면 문제가 없을 수 있으나 모니터링 툴에 문제가 생겨서 로그를 통해 과거의 이용량을 계산하거나, 실시간 처리보다 배치 처리가 더 이득인 상황이 생길 수 있다.
이 경우 더 효율적인 다른 알고리즘이 필요할 것이며, 아무리 효율적이라도 리소스 부하가 심하다면 이러한 경우가 생기지 않도록 예방하려면 어떻게 해야 하는지 깊게 고민해봐야 할 것이다.

프로그램

#include <vector>

using std :: vector ;

int solution ( vector < int > a )
{
    int answer = 2 ;
    int iSize = a.size () ;
    vector < int > vLeftMin ( iSize , 1000000000 ) ;
    vector < int > vRightMin ( iSize , 1000000000 ) ;
    int * ipBallon = a.data () ;
    int iTemp = ipBallon [ 0 ] ;



    if ( iSize <= 2 )
        return iSize ;

    for ( int i = 1 ; i < iSize ; ++i )                // Find left min number
    {
        if ( iTemp > ipBallon [ i - 1 ] )
            iTemp = ipBallon [ i - 1 ] ;
        vLeftMin [ i ] = iTemp ;
    }
    iTemp = ipBallon [ iSize - 1 ] ;
    for ( int i = iSize - 2 ; i >= 0 ; --i )        // Find right min number
    {
        if ( ipBallon [ i + 1 ] < iTemp )
            iTemp = ipBallon [ i + 1 ] ;
        vRightMin [ i ] = iTemp ;
    }

    for ( int i = 1 ; i < iSize - 1 ; ++i )
    {
        if ( ( vLeftMin [ i ] < ipBallon [ i ] ) && ( vRightMin [ i ] < ipBallon [ i ] ) )
            continue ;

        ++ answer ;
    }


    return answer ;
}