소개
음악 스트리밍 회사에서 일하고 있어요.
음악 플레이어 애플리케이션에 사용할 플레이리스트 기능을 만드는 일을 맡게 됐어요.
지침
음악 플레이어 애플리케이션의 프로토타입을 작성해요.
프로토타입에서는 각 노래를 숫자로 나타내요.
숫자 범위(노래 ID)가 주어지면 단방향 연결 리스트를 만들어요.
단방향 연결 리스트가 주어지면, 리스트를 뒤집어서 노래를 반대 순서로 재생할 수 있어야 해요.
연결 리스트는 컴퓨터 과학의 기본적인 자료 구조이며, 다른 자료 구조를 구현할 때 자주 사용돼요.
가장 단순한 연결 리스트는 단방향 연결 리스트예요.
즉, 각 요소(또는 "노드")는 데이터와 함께 리스트의 다음 노드를 가리키는 무언가를 담고 있어요.
연결 리스트에 대해 더 깊이 알아보고 싶다면, 멋진 그림으로 설명해 주는 이 글을 확인해 봐요.
Python에서 이 연습 문제를 구성하는 방식
stacks와 queues는 lists, collections.deque, queue.LifoQueue, multiprocessing.Queue로 구현할 수 있지만, 이 연습 문제에서는 직접 만든 단일 연결 리스트를 사용하는 "후입선출"(LIFO) 스택을 기대해요:
이것은 내부적으로 list, queue, array를 사용할 수도 있는 동적 배열이나 리스트를 사용하는 LIFO 스택과 혼동하면 안 돼요.
동적 배열 기반 stacks는 head 위치가 다르고 시간 복잡도(Big-O)와 메모리 사용량도 달라요.
몇 가지 고려 사항은 다음 두 Stack Overflow 질문을 참고해요: 배열 기반 vs 리스트 기반 스택과 큐, 그리고 배열 스택, 연결 스택, 스택의 차이점.
Python에서 연결 리스트, LIFO 스택, 그리고 다른 추상 자료형(ADT)에 대한 더 자세한 내용은 다음과 같아요:
Python의 클래스
Python에서 연결 리스트를 "정석" 방식으로 구현하려면 보통 하나 이상의 classes가 필요해요.
classes에 대한 좋은 입문 자료로는 classes와 함께 제공되는 연습 문제 ellens-alien-game, 또는 공식 Python 튜토리얼의 클래스 섹션을 참고해요.
Python의 특수 메서드
이 연습 문제의 테스트는 작성한 LinkedList에 len()을 호출해요.
len()이 동작하게 하려면 __len__ 특수 메서드를 만들어야 해요.
Python에서 특수 메서드, 즉 "dunder" 메서드를 구현하는 자세한 방법은 Python 문서: 기본 객체 사용자 정의와 Python 문서: object.len(self)을 참고해요.
이터레이터 만들기
LinkedList를 순회하거나 뒤집으려면 __iter__ 특수 메서드를 구현해야 해요.
구현 세부 사항은 클래스의 이터레이터 구현하기를 참고해요.
예외 사용자 정의와 발생시키기
때로는 코드에서 예외를 사용자 정의하고 raise해야 할 때가 있어요.
이럴 때는 오류의 원인이 무엇인지 알려 주는 의미 있는 오류 메시지를 항상 포함해야 해요.
이렇게 하면 코드가 더 읽기 쉬워지고 디버깅에 큰 도움이 돼요.
사용자 정의 예외는 보통 Exception의 서브클래스인 새로운 예외 클래스를 통해 만들 수 있어요(자세한 내용은 classes 참고).
오류의 원인이 특정 예외 타입 에서 파생된 것임을 아는 경우에는 Exception 클래스 아래에 있는 built in error types 중 하나를 상속받도록 선택할 수 있어요.
오류를 발생시킬 때도 여전히 의미 있는 메시지를 포함해야 해요.
이 연습 문제에서는 연결 리스트가 비어 있을 때 발생되는, 즉 "던져지는" 사용자 정의 예외 를 만들어야 해요.
테스트를 통과하려면 적절한 예외를 사용자 정의하고, 그 예외를 raise하고, 적절한 오류 메시지를 포함해야 해요.
일반 예외 를 사용자 정의하려면 Exception을 상속받는 class를 만들어요.
사용자 정의 예외를 메시지와 함께 발생시킬 때는 메시지를 exception 타입의 인자로 작성해요:
# subclassing Exception to create EmptyListException
class EmptyListException(Exception):
"""Exception raised when the linked list is empty.
message: explanation of the error.
"""
def __init__(self, message):
self.message = message
# raising an EmptyListException
raise EmptyListException("The list is empty.")
