프로그래머스 1차 - 추석트래픽

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

접근

시행착오 1

처음에 문제를 보자마자 그전의 기출을 통해 그리디 알고리즘으로 해결해야 하는 문제인것은 캐치하였으나, 그 이후로 나아가질 못하였다. N의 최대 크기가 2000인 점에서 완전탐색도 어느정도 염두해 두고 문제를 해결해나갔어야 했는데, 그 부분까지 도달하지 못하여 작업을 하나씩 꺼내서 순회하는것을 생각하지 못하였고, 이틀에 걸쳐서 문제를 풀게 되었다. 쉬운 문제라고 생각했는데 역시 카카오 문제가 쉬울리 없지 ㅠ

시행착오 2

for i in range(len(N)):
    count=0
    pres,pree=N[i][0],N[i][1]
    for j in range(len(N)):
        ns,ne=N[j][0],N[j][1]
        if ns<pree+1000:
            count+=1

안일하게 완전탐색으로 N*N으로 계산하였으나 저렇게 작성하면 오류가 발생함. 후반 인덱스로 갈수록 e가 커지기 때문에. ns<pree+1000 이부분이 무조건적으로 참을 반환할 확률이 다분하게 커지기 때문에, 다음과 같이 수정해주어야한다.

for i in range(len(N)):
    count=0
    pres,pree=N[i][0],N[i][1]
    for j in range(i,len(N)):
        ns,ne=N[j][0],N[j][1]
        if ns<pree+1000:
            count+=1

시행착오 3

배열을 순회하는 과정에서 겹치는 작업을 계산할 때 부등호를 ns<=pree+1000 로 작성하였었는데 해당 부분에 오류가 있었다. 왜냐하면 작업은 시작시간과 끝 시간이 포함이므로, 어떤 작업이 끝나자마자 다시 시작한다고 하였을때 count는 1이 되어야 하는것이 정상이지만, 해당 ns<=pree+1000 로직으로 계산하였을 경우 count가 2가 되기때문에 다음과 같이 ns<pree+1000로 수정해 주어야 한다.

전체 코드

def solution(lines):
    N=[]
    maxval=0
    for line in lines:
        line=line.split()
        hms=line[1]
        hms=hms.split(":")
        tosec=int(hms[0])*3600+int(hms[1])*60+float(hms[2])
        tomil=int(tosec*1000)
        spent=int(float(line[2][:-1])*1000)
        start,end=tomil-spent+1,tomil
        N.append([start,end])
    for i in range(len(N)):
        count=0
        pres,pree=N[i][0],N[i][1]
        for j in range(i,len(N)):
            ns,ne=N[j][0],N[j][1]
            if ns<pree+1000:
                count+=1
        maxval=max(maxval,count)
    return maxval

참고

데이터의 갯수가 충분히 작을때는 항상 브루트포스 염두해 두길