240818 - 연속된 부분 수열의 합, 과제 진행하기

[robert-min]

연속된 부분 수열의 합

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

def solution(sequence, k):
    """
    Return : 조건을 만족하는 부분 수열의 시작 인덱스와 마지막 인덱스 
    - 부분 수열의 합 = k
    - 앞쪽 인덱스에서 찾음

    left, right
    합이 k보다 작으면 right 이동
    합이 k보다 크면 left 이동
    합이 == k 이면 [left, right]
    """
    n = len(sequence)
    answer = [0, n]

    left, right = 0, 0
    S = sequence[0]

    while True:
        if S < k:
            right += 1
            if right == n: break
            S += sequence[right]
        else:
            if S == k:
                # 가장 짧은 수열만 답으로 확인
                if right - left < answer[1] - answer[0]:
                    answer = [left, right]
            S -= sequence[left]
            left += 1

    return answer

[robert-min]

과제 진행하기

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

def solution(plans):
    """
    Return : 과제를 끝낸 순서대로 이름 배열
    - 새로운 과제 시작 시간이면 >> 기존 과제X, 새로운 과제
    - 진행 중 과제 끝나면 >> 멈춘 과제 짆애
        - 과제 끝날 시간에 새로운 과제, 기존 과제 있으면 >> 새로운 과제
    - 멈춰둔 과제 있으면, 가장 최근 과제

    """
    from collections import deque

    n = len(plans)

    def convert_time(s):
        h, m = map(int, s.split(":"))
        return h * 60 + m

    table = deque([])
    plans = [(name, convert_time(start), int(playtime)) for name, start, playtime, in plans]
    plans.sort(key = lambda x: x[1])

    Q = deque()
    left_time = 0

    result = []
    for i in range(n):
        # 다음 문제 시작 시간
        name, start, playtime = plans[i]

        # 다음 문제 시작 전까지 이전에 남아 있는 문제 해결
        while Q:
            _name, _playtime = Q.pop()
            if left_time >= _playtime:
                left_time -= _playtime
                result.append(_name)
            else:
                Q.append((_name, _playtime - left_time))
                break

        # 문제 큐에 추가
        Q.append((name, playtime))

        if i < n - 1:
            next_start = plans[i+1][1]
            left_time = next_start - start

    # 다음 풀어야할 문제가 없는 경우 정답에 추가
    while Q:
        _name, _ = Q.pop()
        result.append(_name)

    return result