백준 알고리즘 문제 풀이 가이드: 코딩 면접 대비 완벽 준비-10866 덱(Deque) 편 (python)

문제 살펴보기!!

문제 링크 : https://www.acmicpc.net/problem/10866

반응형

솔루션 살펴보기!!

import sys
from collections import deque

def input():
    return sys.stdin.readline().rstrip()

def process_commands():
    queue = deque()
    N = int(input())
    commands = {
        'push_front': lambda x: queue.appendleft(x),
        'push_back': lambda x: queue.append(x),
        'pop_front': lambda: print(queue.popleft() if queue else -1),
        'pop_back': lambda: print(queue.pop() if queue else -1),
        'size': lambda: print(len(queue)),
        'empty': lambda: print(1 if not queue else 0),
        'front': lambda: print(queue[0] if queue else -1),
        'back': lambda: print(queue[-1] if queue else -1),
    }

    for _ in range(N):
        command = input().split()
        if len(command) == 2:
            commands[command[0]](command[1])
        else:
            commands[command[0]]()

if __name__ == "__main__":
    process_commands()

코드 설명

이 코드는 덱(deque) 자료구조를 사용하여 입력으로 주어진 명령어를 처리하는 프로그램입니다. 덱은 양쪽 끝에서 요소의 삽입과 삭제가 가능한 자료구조로, 파이썬의 collections.deque 모듈을 사용하여 구현됩니다. 이 코드는 다음 명령어를 지원합니다:

• push_front X: 덱의 앞쪽에 X를 삽입
• push_back X: 덱의 뒤쪽에 X를 삽입
• pop_front: 덱의 앞쪽 요소를 제거하고 출력 (덱이 비어있으면 -1 출력)
• pop_back: 덱의 뒤쪽 요소를 제거하고 출력 (덱이 비어있으면 -1 출력)
• size: 덱의 크기를 출력
• empty: 덱이 비어있는지 확인하고 1 또는 0을 출력
• front: 덱의 앞쪽 요소를 출력 (덱이 비어있으면 -1 출력)
• back: 덱의 뒤쪽 요소를 출력 (덱이 비어있으면 -1 출력)

주요 개념

1. 덱 (Deque, Double-Ended Queue):
   덱은 양쪽 끝에서 삽입과 삭제가 가능한 자료구조입니다. collections.deque는 O(1) 시간 복잡도로 삽입과 삭제를 처리할 수 있습니다. 이 프로그램에서 덱을 사용하여 효율적으로 명령을 처리합니다.
2. 딕셔너리를 활용한 명령어 처리:
   각 명령어를 딕셔너리로 매핑하여 명령어 처리에 사용되는 조건문을 줄였습니다. 이렇게 하면 코드가 더 간결해지고 유지보수가 쉬워집니다. 함수형 프로그래밍의 개념을 도입해 명령어에 따라 동작을 매핑하는 것이 핵심입니다.
3. 입력 및 출력 최적화:
   sys.stdin.readline()과 sys.stdout을 사용해 빠른 입력과 출력을 처리합니다. 대규모 입력 데이터를 처리할 때 이 방법이 일반적인 input() 함수보다 더 빠릅니다.

728x90

코드 구조

1. process_commands 함수:
   명령어의 총 개수를 입력받고, 각 명령어에 따라 덱을 조작합니다.
   • 명령어와 그에 해당하는 동작을 딕셔너리로 매핑하여 효율적으로 처리합니다.
   • 각 명령은 split()으로 분리되며, 명령어가 두 개일 경우(예: push_front X)와 하나일 경우(예: size)를 구분하여 적절한 동작을 수행합니다.
2. if __name__ == "__main__"::
   파이썬의 관례로, 이 부분은 현재 파일이 직접 실행될 때 process_commands 함수를 호출하여 프로그램이 시작되도록 합니다.

예상 인터뷰 질문

1. 덱(deque)과 큐(queue)의 차이는 무엇인가요?
   • 답변: 큐는 한쪽에서만 삽입하고 반대쪽에서만 삭제가 가능한 자료구조입니다(First In First Out, FIFO). 반면 덱은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조입니다. 덱은 큐와 스택의 혼합형 자료구조라고 볼 수 있습니다.
2. deque가 리스트(list)보다 성능이 좋은 이유는 무엇인가요?
   • 답변: collections.deque는 양쪽 끝에서의 삽입과 삭제가 O(1) 시간 복잡도를 가집니다. 반면, 파이썬 리스트는 앞쪽에서 삽입이나 삭제가 발생할 경우 O(n)의 시간 복잡도를 가지며, 이는 리스트의 요소를 모두 이동시켜야 하기 때문입니다.
3. 딕셔너리를 사용한 명령어 처리 방식의 장점은 무엇인가요?
   • 답변: 딕셔너리를 사용하면 각 명령어를 간결하게 매핑할 수 있으며, 조건문을 여러 번 사용하는 대신 직접 함수 호출을 할 수 있어 코드가 더 간결해집니다. 이 방식은 특히 명령어가 많아질 때 가독성과 유지보수가 용이합니다.
4. sys.stdin.readline과 일반 input()의 차이는 무엇인가요?
   • 답변: sys.stdin.readline은 대량의 입력을 받을 때 더 빠릅니다. input()은 한 줄을 입력받을 때 문자열을 처리하는 데 추가적인 비용이 들기 때문에 속도가 느릴 수 있습니다. 특히 반복문을 통해 여러 줄을 입력받는 상황에서는 sys.stdin.readline()이 더 효율적입니다.
5. 이 코드의 시간 복잡도는 어떻게 되나요?
   • 답변: 각 명령어는 O(1) 시간 복잡도를 가집니다. 덱의 appendleft, append, popleft, pop 모두 O(1)이며, size, empty, front, back 명령어도 O(1)입니다. 따라서 이 코드는 N개의 명령어에 대해 O(N)의 시간 복잡도를 가집니다.
6. 이 코드의 확장성에 대해 설명해주세요. 예를 들어 새로운 명령어가 추가된다면 어떻게 수정하겠습니까?
   • 답변: 새로운 명령어를 추가하려면 딕셔너리에 해당 명령어와 동작하는 함수를 추가하기만 하면 됩니다. 예를 들어, reverse라는 명령어가 추가된다면 commands['reverse'] = lambda: queue.reverse()와 같이 간단히 추가할 수 있습니다.