[알고리즘] 투 포인터_상담예약제 Python

💡 강의 참고 전 코드 (실패)

# 업무 처리시간 10분

# (1) 현재 시각보다 앞선 시각의 고객 중 업무 시작하는데, 예약고객 우선 시작
# (2) 10분 더했을 때 (1)번 반복

# 시간 : 기준으로 자르기, 분 기준으로 변환, 시간 기준으로 sort
# booked 먼저 탐색, unbooked 그 다음에 탐색
from collections import deque
def solution(booked, unbooked):
    answer = []
    for idx, value in enumerate(booked):
        time, name = value
        h, m = time.split(":")
        mins = 60*int(h) + int(m)
        booked[idx] = [mins, name]
    for idx, value in enumerate(unbooked):
        time, name = value
        h, m = time.split(":")
        mins = 60*int(h) + int(m)
        unbooked[idx] = [mins, name]
    
    booked_dq = deque(sorted(booked, key = lambda x:x[0]))
    unbooked_dq = deque(sorted(unbooked, key = lambda x:x[0]))

    now = 1440
    while (True):
        if len(booked_dq) > 0:
            booked = booked_dq.popleft()
        else:
            booked = False
        while (unbooked_dq):
            unbooked = unbooked_dq.popleft()
            if (now == 1440 and unbooked[0] < booked[0]) or (now != 1440 and unbooked[0] <= now and unbooked[0] >= now) or not booked:
                # unbooked 먼저
                answer.append(unbooked[1])
                if now == 1440:
                    now = (unbooked[0]+10)
                else:
                    now += 10
                booked_dq.appendleft(booked)
            else:
                # booked 먼저
                answer.append(booked[1])
                if now == 1440:
                    now = (booked[0]+10)
                else:
                    now += 10
                unbooked_dq.appendleft(unbooked)
            break
        if len(booked_dq) == 0 and len(unbooked_dq) == 0:
            break

 
    return answer

💡 강사님 풀이

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

후기

풀이가 굉장히 단순하다.
시간을 적절한 숫자로 바꿔주는 부분은 동일하다.
다만 초기 규칙을 단순하게 생각하지 못했다.

✔️ 실수한 점

1️⃣ 반복문에 사용할 자료형

• 나는 deque를 사용했는데 deque를 사용하게 되면 booked unbooked 두가지 중 answer에 추가하지 않은 것을 다시 appendleft 해줘야 하는 문제가 생긴다.
• 여기선 자료형의 길이로 반복문을 돌리는 방식으로 사용했다.

2️⃣ 초기 시간 설정

• 나는 초기 시간을 1440으로 설정했는데, 그럴 필요가 없었다.

✔️ 배운 점

• 특정 자료형을 사용할 때는 그 자료형을 쓰는게 좋을지 다른 자료형을 쓰는게 좋을지 먼저 고민해야 한다.
• 코드를 짜기 전에 풀이 로직을 정리하는데 더 시간을 쓰자.
• 코드가 길어지고 복잡해질 것 같으면 함수로 뺴자
• 강사님 코드의 while문 구조 기억하고 나중에 써먹자 !
• 예외처리 해주기 전에 더미데이터를 추가해서 해결할 수 있는지 확인
• 문법 booked = [[parse_time(time), value] for time, value in booked] + [[10000, 'dummy']] 리스트끼리 더할 떄는 각각 동등한 자료형끼리 더해야 한다 (ex. 이중 리스트 + 이중 리스트)

💡 강의 참고 후 코드

def parse_time(time):
    h, m = time.split(":")
    return (60*int(h) + int(m))

def solution(booked, unbooked):
    b, u, t, answer = 0, 0, 0, []
    booked = [[parse_time(time), value] for time, value in booked] + [[10000, 'dummy']]
    unbooked = [[parse_time(time), value] for time, value in unbooked] + [[10000, 'dummy']]
    booked.sort()
    unbooked.sort()
    
    while b<len(booked) and u<len(unbooked):
        bt, ut = booked[b][0], unbooked[u][0]
        if bt <= t: # 대기중인 손님 중 예약한 손님 우선으로 처리
            answer.append(booked[b][1])
            b += 1
            t += 10
        elif ut <= t:
            answer.append(unbooked[u][1])
            u += 1
            t += 10
        else: # 현재 시점에서 대기중인 손님이 없는 경우
            t = min(bt, ut) # 현재 시간 이후로 올 손님 중 가장 빨리 올 손님 시간으로 설정
            
    answer.pop()
    return answer

더미데이터를 추가해주는 부분은 나중에도 스스로 떠올릴 수 있을지 모르겠다.
잘 쓴 코드들 많이 참고하면서 공부하기 ✔️