[알고리즘] 상담예약제, 티셔츠

상담예약제

정답 해설

풀이계획 : Merge Sort와 비슷한 느낌으로 구현. string의 시간을 적절히 숫자로 바꿔주는 작업 필요.

def parse_time(t):
    h, m = map(int, t.split(':'))
    return 60*h + m

def solution(booked, unbooked):
    
    booked = [(parse_time(t), name) for t, name in booked] + [(1000000, None)]
    unbooked = [(parse_time(t), name) for t, name in unbooked] + [(1000000, None)]
    booked.sort()
    unbooked.sort()
    b, u, t, answer = 0, 0, 0, []
    
    while b < len(booked) and u < len(unbooked):
        
        t1, t2 = booked[b][0], unbooked[u][0]
        if t1 <= t:
            answer.append(booked[b][1])
            b += 1
            t += 10
        elif t2 <= t:
            answer.append(unbooked[u][1])
            u += 1
            t += 10
        else:
            t = min(t1, t2)
    
    answer.pop()
    return answer

solution 함수는 입력으로 booked와 unbooked라는 두 개의 리스트가 주어짐.

각 리스트는 (시간, 이름) 의 형태로 이루어져 있으며, 시간은 "HH:MM" 형식의 문자열.

이 함수는 먼저 입력된 리스트를 parse_time 함수를 이용해 정렬한 뒤, booked와 unbooked 리스트를 하나의 리스트로 합쳐서 새로운 booked와 unbooked 리스트를 생성 -> 마지막 인덱스에는 (1000000, None) 추가.

 

이후, booked와 unbooked 리스트를 정렬하고, booked[b], unbooked[u]에서 각각 예약된 시간 t1, t2를 가져와서 t와 비교.

이때, t는 이전에 예약된 시간에 10분을 더한 시간.

t1, t2 중에서 작은 시간대가 다음 예약 시간이 되어, answer 리스트에 예약한 사람의 이름을 추가하고, t에 10분을 더함.

b와 u는 각각 booked, unbooked 리스트에서 예약된 인원을 가리키는 인덱스.

만약 t1이나 t2가 t보다 크다면, 다음 예약 시간이 되기 전까지 대기.

따라서 t를 t1과 t2 중에서 작은 값으로 업데이트하고, 다시 while문의 조건식으로 돌아가서 다음 예약 시간이 될 때까지 대기.

마지막으로 answer 리스트의 마지막 원소인 None을 제외한 나머지를 반환.

---

티셔츠

정답 해설

풀이 계획 : 작은 사람부터 작은 옷을 입히자.

→ 정렬 후 tshirts을 하나씩 살펴보면서 people보다 크면 입히고, 아니면 넘기기. (투 포인터 활용)

def solution(people, tshirts):
    people.sort()  # 오름차순 정렬
    tshirts.sort()  # 오름차순 정렬
    p, t, ans = 0, 0, 0  # 0 초기화
    while p < len(people) and t < len(tshirts):
        if tshirts[t] >= people[p]:
            ans += 1
            p += 1
        t += 1
    return ans

p 와 t 변수를 각각 people 리스트와 tshirts 리스트에서의 현재 인덱스로 초기화한 후, 두 변수가 리스트 범위 안에서 움직이면서 people[p] 와 tshirts[t] 값을 비교.

 

만약 people[p]가 tshirts[t]보다 작거나 같으면, 해당 사람에게 티셔츠를 나눠줄 수 있으므로 answer 값을 1 증가시키고, p와 t 값을 각각 1씩 증가시켜서 다음 인덱스로 이동.

 

반대로, people[p]가 tshirts[t]보다 크다면, 해당 티셔츠는 더 이상 나눠줄 수 없으므로 t 값을 1 증가시켜서 다음 티셔츠를 확인. 이러한 과정을 리스트를 모두 확인할 때까지 반복.