99클럽 코테 스터디 7일차 TIL, 프로그래머스 / 과제 진행하기

🔑 오늘의 학습 키워드 : 스택

🔗 문제링크 https://school.programmers.co.kr/learn/courses/30/lessons/176962

 

def solution(plans):
    stack = []  # 처리 중인 작업을 저장하는 스택
    answer = []  # 완료된 작업의 순서를 저장하는 리스트
    
    # 시간 및 소요 시간 정리
    for i in range(len(plans)):
        h, m = map(int, plans[i][1].split(':'))  # 시작 시간을 시간과 분으로 분리
        plans[i][1] = h * 60 + m  # 시작 시간을 분 단위로 변환
        plans[i][2] = int(plans[i][2])  # 소요 시간을 정수형으로 변환
    
    # 작업들을 시작 시간 기준으로 정렬
    plans.sort(key=lambda x: x[1])
    
    # 작업 처리
    for i in range(len(plans) - 1):
        stack.append([plans[i][0], plans[i][2]])  # 작업 이름과 남은 소요 시간을 스택에 추가
        gap = plans[i + 1][1] - plans[i][1]  # 다음 작업까지의 시간 간격을 계산
        
        # 현재 시간 간격 내에 스택의 작업을 처리
        while stack and gap:
            if stack[-1][1] <= gap:  # 스택의 마지막 작업이 간격 내에 완료될 수 있는 경우
                cn, ct = stack.pop()  # 작업을 스택에서 꺼내서
                gap -= ct  # 남은 시간에서 해당 작업의 소요 시간을 빼고
                answer.append(cn)  # 완료된 작업 리스트에 추가
            else:
                stack[-1][1] -= gap  # 스택의 마지막 작업을 간격 내에서 가능한 만큼 수행
                gap = 0  # 시간이 다 되었으므로 종료
    
    # 마지막 작업 처리
    answer.append(plans[-1][0])  # 마지막 작업은 무조건 완료되므로 추가
    
    # 스택에 남은 작업들을 뒤에서부터 순서대로 완료 리스트에 추가
    for i in range(len(stack)):
        answer.append(stack[~i][0])
    
    return answer

 

🗒️ 공부한 내용 본인의 언어로 정리하기

🤔 문제를 보고 든 생각

오래전에 푼 문제라 기억이 안난다

 

⏰ 예상 시간 복잡도 O(N)

제한 사항

3 ≤ plans의 길이 ≤ 1,000
plans의 원소는 [name, start, playtime]의 구조로 이루어져 있습니다.
name : 과제의 이름을 의미합니다.
2 ≤ name의 길이 ≤ 10
name은 알파벳 소문자로만 이루어져 있습니다.
name이 중복되는 원소는 없습니다.
start : 과제의 시작 시각을 나타냅니다.
"hh:mm"의 형태로 "00:00" ~ "23:59" 사이의 시간값만 들어가 있습니다.
모든 과제의 시작 시각은 달라서 겹칠 일이 없습니다.
과제는 "00:00" ... "23:59" 순으로 시작하면 됩니다. 즉, 시와 분의 값이 작을수록 더 빨리 시작한 과제입니다.
playtime : 과제를 마치는데 걸리는 시간을 의미하며, 단위는 분입니다.
1 ≤ playtime ≤ 100
playtime은 0으로 시작하지 않습니다.
배열은 시간순으로 정렬되어 있지 않을 수 있습니다.

😎 알고리즘 개요

작업 시간을 분 단위로 정렬하고 스택에 담아가면서 하면 된다

 

✅ 오늘의 회고

 

- 스택에서 ~i를 통한 비트연산자로 맨 위에서부터 더할 수 있었다

 

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL