프로그래머스 추석 트래픽

tiki·2021년 6월 28일

프로그래머스

목록 보기

5/5

코드

def solution(lines):
    answer = 0
    logData = []
    timeList = []

    for index in range(len(lines)):
        
        days, time, duration = lines[index].split(" ")
        hour, minute, second = time.split(":")
        endTime = int((int(hour)*3600 + int(minute)*60 + float(second))*1000)
        durationList = list(duration)
        durationList.pop()
        durationTime = float("".join(durationList))
        
        startTime = endTime - int(durationTime*1000) + 1
        
        logData.append((startTime, endTime))
 
        if startTime == endTime:
            timeList.append(startTime)
        else:
            timeList.append(startTime)
            timeList.append(endTime)
        
    logData = sorted(logData)
    timeList = sorted(timeList)
 
    
    for i in range(len(timeList)):
    
        time = timeList[i]
        addOneSecond = time + 999
        count = 0
        for v in range(len(logData)):
            start_time, end_time = logData[v]
            
            if addOneSecond >= start_time and time <= end_time:
                count += 1
            else:
                if addOneSecond < start_time:
                    break
        answer = max(answer, count)
        
    return answer

문제풀이

주어진 시간에 대한 로그 값을 통해서 최대 처리량을 분석하는 문제이다.
각 로그값이 시간에 대한 형식을 맞추어서 되어 있기 때문에 해당 값을 우선 파싱하는 것이 우선이다. 이때 소수점 자리의 초를 이용하게 되는데 이것 때문에 이 문제를 푸는 것에 애를 먹었다.

❓ 부동 소수점

프로그래밍 언어는 IEEE 754라는 국제표준에 따라 실수를 부동소수점 방식으로 표현한다. 부동소수점 방식에서는 숫자를 정수로 된 유효숫자와 정수로 된 지수의 곱으로 표현한다.

파이썬에서는 이를 float 라는 타입을 통해서 나타내고 있다.

부동 소수점의 오차

보다 작은 수의 경우에는 십진법으로 간단히 표현되는 수도 이진법에서는 무한개의 유효숫자를 가질 수 있다. 예를 들어 0.1 이라는 숫자는 십진수로는 간단히 표현되지만 이진수로 나타내면 다음과 같이 0011(2) 이 무한히 반복되는 실수가 된다.

0.1=0.00011001100110011001100110011001100110011001100110011001100110011⋯(2)

그런데 컴퓨터에서는 하나의 숫자를 나타내기 위한 메모리 크기가 제한되어 있어서 특정 소수점 이하는 생략하고 가장 비슷한 숫자로 표현할 수 밖에 없다. 0.1은 실제로는 가장 비슷한 다음과 같은 숫자로 저장된다.

0.1≈0.1000000000000000055511151231257827021181583404541015625

이에 따라서 우리의 눈에 보여지는 것과는 오차가 조금씩 있다는 것이다.

🔧 부동 소수점의 이해와 문제 풀이 방법 교체

이 문제에서는 시간이 같은 순간에 대해서도 카운트를 해주어야하는데 부동 소수점으로 인한 오차가 발생하면 부등식이 제대로 먹히지 않는 예시들이 있다. 따라서 float 자료형을 사용하지 않도록 했고, 모두 다 int 정수형으로 고쳐주었다.

문제를 푸는 알고리즘

1초의 시간 간격을 통해서 가장 최고로 처리과정에 있는 순간을 구하는 것이다. 따라서 같은 개수라도 그러한 순간은 여러가지 존재할 수 있다.

그래서 시작시간과 끝나는 지점을 기준으로만 최대 처리량을 계산하기로 했다.

주어진 log 데이터를 int형으로 변환한다.
(시작 시간, 끝나는 시간) 배열을 한개 만들어 주고, 각 시간의 구분 없이 추가한 배열도 만든다.
두 배열을 모두 시간에 대한 오름차순으로 정리해준다.
반복문을 통해서 각 시간에 대한 최대 처리량을 계산해준다. 여기서 반복적인 계산이 나타날 수 있으므로 만약 해당하는 값이 아니라면 반복을 종료하는 코드로 같이 작성한다.

tiki

하루하루 조금씩 발전하려는 개발자 입니다.

이전 포스트

프로그래머스 추석 트래픽