[Python] '파티에 참석하기 가장 좋은 시간' 알고리즘 연습문제

Srini Devadas의 '퍼즐로 배우는 알고리즘 with 파이썬'에서 두 번째 퍼즐 '파티에 참석하기 가장 좋은시간'의 연습문제를 풀어보았습니당

 

연습문제 1)

파티에 갈 수 있는 시간(ystart시-yend시) 안에서 가장 많은 연예인을 만날 수 있는 시간과 그 때의 연예인의 수를 찾도록 코드를 짜 보아라. 여기에서 입력값으로 주어지는 구간은 [ystart, yend)라고 하자.

 

def bestTimeToPartyforMe(schedule, ystart, yend):
 
    csched = schedule.copy()
 
    for c in csched:
        if c[1] <= ystart or c[0]>=yend:
            csched.remove(c)
    print(csched)
 
    times = []
    for c in csched:
        times.append((c[0], 'start'))
        times.append((c[1], 'end'))
      
    sortList(times)    
    maxcount, time = chooseTime(times)
    
    print(f"당신이 파티에 있는 시간 중 {time}시에서 가장 많은 {maxcount}명의 연예인을 만날 수 있습니다!")
 
def sortList(tlist):
    for ind in range(len(tlist)-1):
        iSm = ind
        for i in range(ind, len(tlist)):
            if tlist[iSm][0] > tlist[i][0]:
                iSm = i
        tlist[ind], tlist[iSm] = tlist[iSm], tlist[ind]
 
def chooseTime(times):
    rcount = 0
    maxcount = time = 0
 
    for t in times:
        if t[1] == 'start':
            rcount = rcount + 1
        elif t[1] == 'end':
            rcount = rcount -1
        if rcount > maxcount:
            maxcount = rcount
            time = t[0]
    return maxcount, time        
 

 

연습문제 2)

시간 단위에 의존하지 않고 파티에 갈 수 있는 최적의 시간을 찾는 기존의 방법과 달리, 차례차례 연예인 한 명씩 선택하여 이의 시작시간이 얼마나 많은 연예인의 존재 구간에 포함되는지 계산하여 파티에 갈 시간을 결정하는 알고리즘을 구현하라.

 

sched2 = [(6.0, 8.0), (6.5, 12.0), (6.5, 7.0), (7.0, 8.0), (7.5, 10.0), (8.0, 9.0),
         (8.0, 10.0), (9.0, 12.0), (9.5, 10.0), (10.0, 11.0), (10.0, 12.0), (11.0, 12.0)]
 
def compareArrivingTime(schedule):
    
    starttime = []
    endtime = []
    for c in schedule:
        starttime.append((c[0]))
        endtime.append((c[1]))
        
    count = [0]*len(starttime)
 
    for s in range(len(starttime)):
        for i in range(len(starttime)):
            if (starttime[i] <= starttime[s] < endtime[i]) == True:
                count[s]+=1
    
    maxC = time = 0
    for i in range(len(count)):
        if count[i] > maxC:
            maxC = count[i]
            time = i    
    
    print(f"파티를 가야하는 시간은 {starttime[time]}이며, 이 때 {maxC}명의 연예인을 만날 수 있습니다.")
    
 

 

연습문제 3)

파티에 만날 연예인들에 대해 본인의 선호도가 있다고 가정하자. 예를 들어 (6.0, 8.0, 3)이라면 6.0은 도착 시간, 8.0은 떠나는 시간, 그리고 3은 본인이 이 연예인을 얼마나 좋아하는지를 나타낸다. 코드를 수정해서 가장 많은 선호도를 가지는 시간을 찾을 수 있도록 해 보아라.

주어진 연예인 스케쥴에서, 당신은 최대 선호도 13을 얻을 수 있도록 11.0시 정각에 가야 한다.

 

sched3 = [(6.0, 8.0, 2), (6.5, 12.0, 1), (6.5, 7.0, 2),
         (7.0, 8.0, 2),(7.5, 10.0, 3),(8.0, 9.0, 2),
         (8.0, 10.0, 1),(9.0, 12.0, 2), (9.5, 10.0, 4),
         (10.0, 11.0, 2), (10.0, 12.0, 3),(11.0, 12.0, 7)]
 
def bestPreferedTime(schedule):
    
    starttime = []
    endtime = []
    prefered = []
    
    for c in schedule:
        starttime.append((c[0]))
        endtime.append((c[1]))
        prefered.append(c[2])
        
    prefered_sum = [0]*len(prefered)
 
    for s in range(len(starttime)):
        for i in range(len(starttime)):
            if (starttime[i] <= starttime[s] < endtime[i]) == True:
                prefered_sum[s] += prefered[i]
 
    maxP = time = 0
    for i in range(len(prefered_sum)):
        if prefered_sum[i] > maxP:
            maxP = prefered_sum[i]
            time = i    
        
    print(f"파티를 가야하는 시간은 {starttime[time]}이며, 이 때 {maxP}의 선호도를 얻을 수 있습니다.")
 

 

얼마나 효율적인지는 잘 모르겠고 일단 책 한바퀴 다 돌고 다시 한번 수정해야 할 것 같은...

 

 

*이전 포스트를 참고해 주세요.