[프로그래머스] 과제 진행하기 - Lv.2

프로그래머스 176962번 문제인 "과제 진행하기" Lv.2을 파이썬으로 풀어보도록 하겠습니다.

[프로그래머스] 과제 진행하기 Lv.2 - [파이썬/python]

 

 

프로그래머스-과제-진행하기

---

💻 문제 설명

 

과제를 받은 루는 다음과 같은 순서대로 과제를 하려고 계획을 세웠습니다.

 

• 과제는 시작하기로 한 시각이 되면 시작합니다.
• 새로운 과제를 시작할 시각이 되었을 때, 기존에 진행 중이던 과제가 있다면 진행 중이던 과제를 멈추고 새로운 과제를 시작합니다.
• 진행중이던 과제를 끝냈을 때, 잠시 멈춘 과제가 있다면, 멈춰둔 과제를 이어서 진행합니다.
  • 만약, 과제를 끝낸 시각에 새로 시작해야 되는 과제와 잠시 멈춰둔 과제가 모두 있다면, 새로 시작해야 하는 과제부터 진행합니다.
• 멈춰둔 과제가 여러 개일 경우, 가장 최근에 멈춘 과제부터 시작합니다.

과제 계획을 담은 이차원 문자열 배열 plans가 매개변수로 주어질 때, 과제를 끝낸 순서대로 이름을 배열에 담아 반환(return) 하는 solution 함수를 완성해주세요.

 

https://school.programmers.co.kr/learn/courses/30/lessons/176962

프로그래머스

---

🚨 제한사항

 

• 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으로 시작하지 않습니다.
    • 배열은 시간순으로 정렬되어 있지 않을 수 있습니다.
• 진행중이던 과제가 끝나는 시각과 새로운 과제를 시작해야하는 시각이 같은 경우 진행중이던 과제는 끝난 것으로 판단합니다.

---

 

 

---

---

---

!!!정답 주의!!!

---

---

---

 

 

 

---

🌟 소스 코드

 

 

 

 

def solution(plans):

   

    # 과제를 시작 시간 내림차순 정렬합니다. (deque 쓰기 귀찮아서)

    plans.sort(key=lambda x: x[1], reverse=True)

    stop_plans = [] # 잠시 멈춘 과제를 저장할 stack

    result = [] # 결과를 저장할 리스트

   

    # 시간을 분 단위로 변환하는 함수

    def convert_to_minutes(time):

        hours, minutes = map(int, time.split(':'))

        return hours * 60 + minutes

       

    # 모든 과제를 처리할 때까지 반복

    while len(plans) >= 2:

       

        # 현재 과제의 정보(과목의 이름, 과제의 시작 시간, 과제 마치는데 걸리는 시간(분))

        name = plans[-1][0]

        start = convert_to_minutes(plans[-1][1])

        playtime = int(plans[-1][2])

       

        # 다음 과제의 시작 시간

        next_start = convert_to_minutes(plans[-2][1])

       

        # 현재 과제를 마치고 남은 시간

        spare_time = next_start - (start + playtime)

       

        # 남은 시간이 충분하다면 현재 과제를 완료하고 result에 추가

        if spare_time >= 0:

            result.append(name)

            plans.pop()

           

            # 남은 시간 동안 잠시 멈춘 과제를 처리

            # 과제 다 마치면 result에 추가 및 stop_plans에서도 삭제

            # 과제 다 못 마치면 playtime에서 여유시간만큼 차감

            while spare_time > 0 and stop_plans:

               

                if spare_time >= stop_plans[-1][1]:

                    spare_time -= stop_plans[-1][1]

                    result.append(stop_plans.pop()[0])

                   

                else:

                    stop_plans[-1][1] -= spare_time

                    break

       

        # 남은 시간이 부족하다면 현재 과제를 잠시 멈추고 stop_plans에 추가

        else:

            stop_plans.append([name, playtime - (next_start - start)])

            plans.pop()

   

    # 마지막 과제를 result 추가

    result.append(plans.pop()[0])

   

    # 잠시 멈춘 과제가 남아 있다면 result 추가

    result.extend(name for name, playtime in reversed(stop_plans))

   

    return result

 

 

 

---

⏱ 시간복잡도

 

위 코드의 시간복잡도는 O(n log n)입니다.

 

 

과제 정렬하기: plans.sort(key=lambda x: x[1], reverse=True)

과제를 시작 시간 순서대로 정렬하는 데는 O(n log n)의 시간이 소요됩니다. 여기서 n은 과제의 수입니다.

 

반복문 순회하기: while len(plans) >= 2:

모든 과제를 처리할 때까지 반복문을 순회하는 데는 O(n)의 시간이 소요됩니다.

 

리스트에 넣고, 빼기: append(), pop()

리스트의 끝에 요소를 추가하는 append 연산은 일반적으로 상수 시간, 즉 O(1)의 시간 복잡도를 가집니다. 이는 추가하는 요소의 크기에 관계없이 거의 동일한 시간이 소요되기 때문입니다.

리스트의 끝에서 요소를 제거하는 pop 연산 또한 상수 시간, 즉 O(1)의 시간 복잡도를 가집니다. 이는 제거하는 요소의 위치에 관계없이 거의 동일한 시간이 소요되기 때문입니다.

 

조건문 확인하기: f spare_time >= 0:

각 반복마다 조건문을 확인하는 데는 상수 시간, 즉 O(1)의 시간이 소요됩니다.

 

잠시 멈춘 과제 처리하기: while spare_time > 0 and stop_plans:

남은 시간 동안 잠시 멈춘 과제를 처리하는 데는 최악의 경우 O(n)의 시간이 소요될 수 있습니다. 여기서 n은 잠시 멈춘 과제의 수입니다.

 

따라서, 이 코드는 과제를 한 번만 순회하고, 각 과제에 대해 상수 시간의 연산을 수행하므로, 전체 시간 복잡도는 O(n log n + n + n)입니다. 그러나 보통 복잡도에서는 가장 큰 항만을 고려하므로, 이 코드의 시간 복잡도는 O(n log n)으로 간주할 수 있습니다. 이는 입력 크기에 대해 로그 선형적으로 비례하는 시간 복잡도를 의미합니다.

---

🏳‍🌈 테스트 결과

 

프로그래머스-과제-진행하기-상태

 

프로그래머스-과제-진행하기-테스트-결과