[コードテスト]2018 KAKAO BLIND RECRUITMENT[1]秋夕流量

問題の説明

中秋節の流量
今年の秋夕(チュソク、陰暦8月15日)にシステム障害のない祝日を過ごすために、Apacheはサーバーの増設を悩んでいる.障害対応サーバーを増設するかどうかを決めるため、昨年秋夕(チュソク、陰暦8月15日)、9月15日にログデータを分析した後、1秒当たりの最大スループットを算出することにした.1秒あたりの最大スループットは、要求が応答を完了するかどうかにかかわらず、任意の時間から1秒(=1000ミリ秒)の要求を処理する最大数を意味します.
入力フォーマット
solution関数に渡されるlines配列はN(1≦N≦2000)個のログ文字列からなり、各ログ文字列は要求に対する応答完了時間Sと処理時間Tをスペースで区切っている.
応答完了時間Sは昨年秋夕2016年9月15日のみで、固定長2016-09-15 hh:mm:ss.sss形式で存在する.
処理時間Tは、0.1 s,0.312 s,2 sのように最大小数点の3番目のビットに記録され、後に秒単位を示すsが続く.
例えば、ログ文字列2016-09-1503:10:33.00 0.011 sは、「2016年9月15日午前3時10分33.00秒」から「2016年9月15日午前3時10分33.00秒」、「0.011秒」の間に処理されるリクエストを意味する.(処理時間は開始時間と終了時間を含む)
サーバ上のタイムアウト時間は3秒であるため、処理時間は0.001≦T≦3.000である.
lines配列は、応答完了時間Sを基準として昇順に配列されている.
出力フォーマット
solution関数は、ログデータ線アレイに対して毎秒最大スループットを返します.

に答える

質問を読んだ後、「文字列でこれを時間内に含めるかどうかを判断するのは面倒でしょう」と思いました.という考えが生まれた.そこで,入力ログの開始時間と終了時間を実数形式に変換する関数を以下に示す.

def convert(line):
    h, m, s = line.split(' ')[1].split(':')
    end = round(3600 * float(h) + 60 * float(m) + float(s), 3)
    ran = float(line.split(' ')[2][:-1])
    return round(end - ran + 0.001, 3), end

実数で保存すると、以下の簡単な比較演算子で含めるかどうかを判断できるので、簡単に解決できます.

def solution(lines):
    answer = 1
    for idx, line in enumerate(lines):
        start, end = convert(line)
        startCount = 1
        endCount = 1
        for nextIdx in range(idx + 1, len(lines)):
            nextStart, nextEnd = convert(lines[nextIdx])
            startCount += 0 if nextEnd < start or 
                start + 0.999 < nextStart else 1
            endCount += 0 if nextEnd < end or 
                end + 0.999 < nextStart else 1
        answer = max(answer, max(startCount, endCount))
    return answer

しかし、いくつかのテストケースでは、基数値と結アップル値が一致せず、ポーリングコードを記述してデバッグした後、浮動小数点演算により得られた結果は予想とは異なる(ex 1+0.999->1.999999999997).一瞬前、Pythonでは浮動小数点演算がホットスポットだったのを覚えていますが、比較演算子を勝手に使うと予想外の結果が出ます.解決策はround関数を用いて小数点4ビット以下の演算を排除し,コードを以下のように修正することである.

def convert(line):
    h, m, s = line.split(' ')[1].split(':')
    end = round(3600 * float(h) + 60 * float(m) + float(s), 3)
    ran = float(line.split(' ')[2][:-1])
    return round(end - ran + 0.001, 3), end


def solution(lines):
    answer = 1
    for idx, line in enumerate(lines):
        start, end = convert(line)
        startCount = 1
        endCount = 1
        for nextIdx in range(idx + 1, len(lines)):
            nextStart, nextEnd = convert(lines[nextIdx])
            startCount += 0 if nextEnd < start or round(
                start + 0.999, 3) < nextStart else 1
            endCount += 0 if nextEnd < end or round(
                end + 0.999, 3) < nextStart else 1
        answer = max(answer, max(startCount, endCount))
    return answer