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

 Srini Devadas의 '퍼즐로 배우는 알고리즘 with 파이썬' 두번째 퍼즐!

'파티에 참석하기 가장 좋은 시간' 고르기 문제이다.

 

 만약 많은 연예인이 참가하는 파티의 티켓을 얻었다면 가장 많은 연예인을 만날 수 있는, 파티에 참석하기 가장 좋은 시간은 언제일지 구하는 문제이다.

 

 12명의 연예인이 참석한다고 할 때, (6,8)과 같은 튜플에서 첫 원소는 도착하는 시간(포함), 두 번째 원소는 떠나는 시간(포함하지 않음) 이라고 한다면 각각의 튜플을 보고 어떻게 가장 적절한 파티 참석시간을 고를 수 있을까?

 

 

1.  시간이 정수형일 때

 

sched = [(6,8), (6,12), (6,7), (7,8), (7,10), (8,9), (8,10), (9,12), (9,10), (10,11), (10,12), 
         (11,12)]
 
def bestTimeToParty(schedule):
    start = schedule[0][0]
    end = schedule[0][1]
    
    for c in schedule:
        start = min(c[0], start)
        end = max(c[1], end)
    count = celebrityDensity(schedule, start, end)
    maxcount = 0
    for i in range(start, end + 1):
        if count[i] > maxcount:
            maxcount = count[i]
            time = i
    
    print('Best time to attend the party is at', time, 'o\' clock : ', maxcount, 
          'celebrities will be attending!')
 
def celebrityDensity(sched, start, end):
    count = [0] * (end + 1)
    for i in range(start, end+1):
        count[i] = 0
        for c in sched:
            if c[0] <= i and c[1] > i:
                count[i] +=1
    return count

 

(8-10)  매개변수로 받은 schedule 안에서 가장 작은 start와 가장 큰 end를 구해 저장한다.

 

(11)     celebrityDensity에서 전체 시간대 별로 파티에 있는 연예인의 수를 구한다.

예를 들어 start와 end 범위 내에 있는 값인 8이 i라고 했을 때, schedule에 있는 어느 한 연예인의 start 시간보다 i가 크고, end 시간보다 i가 작다면 해당 연예인은 i시간 대에 파티 내에 상주해 있는 것이므로 count[i]를 1 올려준다.

 

(12-16) celebrityDensity가 리턴해 준 count 배열에서 가장 큰 값을 maxcount에 저장, 가장 큰 값의 인덱스를 time에 저장해서 출력해주면 끝!

 

bestTimeToParty(sched1)의 결과는 다음과 같다.

  "Best time to attend the party is at 9 o'clock : 5 celebrities will be attending!"  

 

 

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 bestTimeToPartySmart(schedule):
    times = []
    for c in schedule:
        times.append((c[0], 'start'))
        times.append((c[1], 'end'))
    sortList(times)
    maxcount, time = chooseTime(times)
    print('Best time to attend the party is at', time, 'o\' clock : ', maxcount, 
          'celebrities will be attending!')
    
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        

 

(bestTimeToPartySmart)

매개변수 schedule의 각 튜플을 받아서 times에 (도착시간, 'start')와 (떠나는 시간, 'end')로 분리하여 넣어준다.

sortList에서 times를 시간 순서로 정렬해주면, chooseTime에서 연예인이 가장 많은 시간대와 그 때의 연예인의 수를 도출해준다.

 

(chooseTime)

 times에는 12명의 도착, 떠나는 시간의 튜플이 들어있으므로 총 24개의 튜플이 있다. times의 인덱스를 올려가면서 start의 튜플을 만나면 +1, end의 튜플을 만나면 -1을 하는 방식으로 rcount를 계산해 보았을 때 start가 end의 수보다 더 많다는 것은 즉 파티 장소에 도착해서 떠나지 않은 연예인들이 존재한다는 의미가 된다.