Assignment 1 - Process packages

Assignment 1 - Process packages

이번에는 문제 3의 Process packages에 대해 풀어본다.

일단 Advanced Problem이라는 명칭에서부터 어려움을 직감할 수 있다.
Network상에서 데이터 패킷을 전달하고 버퍼를 통해 연산을 진행할 때 버퍼의 수에 따라 연산 시간에 따라 처리되는 시점을 혹은 처리가 되지 않음을 반환하는 업무이다. 여기서 4개의 중요 인자가 있다.

i   : packet number
Ai : arrived time
Pi : time to process
S : buffer size

이 인자들을 활용하여 밑의 예시를 설명한다.

우선 위의 인자들이 입력되는 패턴은 아래와 같다.

따라서 첫줄의 내용이 버퍼크기(S)와 패킷 갯수(i)가 된다. 이후에 입력되는 양은 i와 같고 각각 도달시각(Ai), 처리시간(Pi)가 된다. 첫번째 샘플은 버퍼크기가 1이지만 패킷 갯수는 0이므로 바로 빠져나오게 된다.

샘플 3을 보게되면 버퍼크기는 1이며 패킷갯수는 2개인 상태에서 [0 1] [0 1]의 패킷이 도달한다. 하지만 동시 0초에 도착하므로 버퍼 크기가 1인상태에서는 먼저 도달한 한개의 패킷만 홀딩가능하다. 따라서 첫번째 패킷은 시작시점인 0이 출력, 두번째 패킷은 drop된다.(-1)

간단해 보이지만 버퍼 크기가 증가하고 패킷 갯수가 늘어날 수록 코드가 복잡하게 작성될 수 밖에 없음을 암시한다.

바로 코드로 넘어가면

# python3
from collections import namedtuple

Request = namedtuple("Request", ["arrived_at", "time_to_process"])
Response = namedtuple("Response", ["was_dropped", "started_at"])


class Buffer:
    def __init__(self, size):
        self.size = size
        self.finish_time = []

    def process(self, request):
        # write your code here
        return Response(False, -1)


def process_requests(requests, buffer):
    responses = []
    for request in requests:
        responses.append(buffer.process(request))
    return responses


def main():
    buffer_size, n_requests = map(int, input().split())
    requests = []
    for _ in range(n_requests):
        arrived_at, time_to_process = map(int, input().split())
        requests.append(Request(arrived_at, time_to_process))

    buffer = Buffer(buffer_size)
    responses = process_requests(requests, buffer)

    for response in responses:
        print(response.started_at if not response.was_dropped else -1)


if __name__ == "__main__":
    main()

위와 같은 형태로 나와 있는 것을 볼 수 있다. 이번에도 Request, Response라는 데이터타입을 정의하면서 정보를 효율적으로 다루기위한 준비가 되어있음을 알 수 있다. 이후 버퍼에 변수는 size와 finish_time이 있으며 process 메쏘드를 수정하여 완성하여야 한다.

이후 main함수는 딱히 건드릴 필요가 없어 보이며 큰 흐름은 먼저 버퍼 크기와 패킷 갯수를 입력받은 뒤 도달시각, 처리시간을 각각 Request 타입으로 묶어 requests에 저장한다. 그리고 버퍼에서 requests에 대해 처리를 한 값들을 responses로 받고 이에 대해 적합한 값(시작시각 or drop여부)를 순차적으로 출력해준다.

# python3
from collections import namedtuple

Request = namedtuple("Request", ["arrived_at", "time_to_process"])
Response = namedtuple("Response", ["was_dropped", "started_at"])


class Buffer:
    def __init__(self, size):
        self.size = size
        self.finish_time = []

    def process(self, request):
        # write your code here
        if len(self.finish_time) > self.size:
            return Response(True, -1)
        elif len(self.finish_time) < self.size:
            self.finish_time.append(int(request.arrived_at) + int(request.time_to_process))
            return Response(False, request.arrived_at)
        else:
            if not [i for i in self.finish_time if i <= request.arrived_at]:
                return Response(True, -1)
            else:
                del self.finish_time[0]
                self.finish_time.append(int(request.arrived_at) + int(request.time_to_process))
                return Response(False, request.arrived_at)


def process_requests(requests, buffer):
    responses = []
    for request in requests:
        responses.append(buffer.process(request))
    return responses


def main():
    buffer_size, n_requests = map(int, input().split())
    requests = []
    for _ in range(n_requests):
        arrived_at, time_to_process = map(int, input().split())
        requests.append(Request(arrived_at, time_to_process))

    buffer = Buffer(buffer_size)
    responses = process_requests(requests, buffer)

    for response in responses:
        print(response.started_at if not response.was_dropped else -1)


if __name__ == "__main__":
    main()

중간의 코드 상태이다. 위에 간단한 예시들은 통과했지만 버퍼 크기와 패킷 갯수가 증가하자 처리하지 못하는 상황이 발생했다.

# python3
from collections import namedtuple

Request = namedtuple("Request", ["arrived_at", "time_to_process"])
Response = namedtuple("Response", ["was_dropped", "started_at"])


class Buffer:
    def __init__(self, size):
        self.size = size
        self.finish_time = []

    def process(self, request):
        # write your code here
        if not self.finish_time:
            self.finish_time.append(request)
            return Response(False, request.arrived_at)

        else:
            if self.finish_time[0][1] <= request[0]:
                for i in range(len(self.finish_time)-1, -1, -1):
                    if self.finish_time[i][1] <= request[0]:
                        del self.finish_time[i]

                if not self.finish_time:
                    self.finish_time.append(Request(request.arrived_at, 

                                            int(request.arrived_at)+int(request.time_to_process)))
                    return Response(False, self.finish_time[-1][0])

                else:
                    self.finish_time.append(Request(self.finish_time[-1][1], 

                                            int(self.finish_time[-1][1])+int(request.time_to_process)))
                    return Response(False, self.finish_time[-1][0])

            else:
                if len(self.finish_time) == self.size:
                    return Response(True, -1)

                else:
                    self.finish_time.append(Request(self.finish_time[-1][1], 

                                            int(self.finish_time[-1][1])+int(request.time_to_process)))

                return Response(False, self.finish_time[-1][0])


def process_requests(requests, buffer):
    responses = []
    for request in requests:
        responses.append(buffer.process(request))
    return responses


def main():
    buffer_size, n_requests = map(int, input().split())
    requests = []
    for _ in range(n_requests):
        arrived_at, time_to_process = map(int, input().split())
        requests.append(Request(arrived_at, time_to_process))

    buffer = Buffer(buffer_size)
    responses = process_requests(requests, buffer)

    for response in responses:
        print(response.started_at if not response.was_dropped else -1)


if __name__ == "__main__":
    main()

최종 코드이며 모든 test set을 통과하였다. 통일성을 위하여 process 메쏘드만 변경하였다.

먼저 초기 if문에서는 self.finish_time 리스트가 비어있다면 인자로 받아온 request를 그대로 리스트에 추가하고 리턴값으로는 Response로 False와 request.arrived_at를 반환한다.

이외의 상황에서는 크게 self.finish_time[0][1] 요소가 request[0]의 값보다 작거나 같은 경우와 아닌경우로 나누었다. 이는 finish_time리스트의 첫번째 요소를 삭제할 수 있는지 없는지 여부를 확인하는 것이다.

만약 그럴 경우 먼저 for문을 통해 리스트 내에서 해당 request time(request[0])의 기준에 의해 finish_time 리스트 내에 총 처리시간을 초과한 요소들을 제거해나간다.

그 후 finish_time 리스트가 비었거나 비지 않았거나 비슷하게 finish_time에 Request 타입을 통해 새로운 arrived_at과 time_to_process를 묶어 추가한다. (비었다면 arrived_at은 request.arrived_at이 그대로 전달, 아니면 finish_time의 마지막 time_to_process를 전달하는 차이)

그리고 삭제할 요소가 없는 경우엔 또 다시 두가지로 나뉘는데 그 기준은 finish_time 리스트가 꽉 차있는지 여부이다. 꽉 차있다면 패킷은 더이상 버퍼에 들어갈 수 없기 때문에 Response에 True와 -1을 담아 반환하고 그 이외에는 위의 규칙과 비슷하게 진행한다.

굉장히 많은 시간을 소요했지만 해결한 만큼 보람찬 과제였다.

제출이 완료되었고 채점이 완료된 상태를 추후에 업데이트 해야겠다.

업데이트

아래와 같이 일단 패스는 하였고 대신 푼 것이 2개라 딱 2개 모두 맞춘 것을 알 수 있다.