오늘 문제는 덱 자료 구조의 기본 기능들을 직접적으로 활용하는 문제입니다.
1. 오늘의 학습 키워드
- 덱
2. 문제: 회전하는 큐 (1021번)
- 단계: 🥈실버 3티어
- 알고리즘 분류: 자료 구조, 덱
- 출처: https://www.acmicpc.net/problem/1021
회전하는 큐
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 47894 | 28823 | 23514 | 61.762% |
문제
입력
첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.
출력
첫째 줄에 문제의 정답을 출력한다.
예제 입력 1 복사
10 3
1 2 3
예제 출력 1 복사
0
예제 입력 2 복사
10 3
2 9 5
예제 출력 2 복사
8
예제 입력 3 복사
32 6
27 16 30 11 6 23
예제 출력 3 복사
59
예제 입력 4 복사
10 10
1 6 3 2 7 9 8 4 10 5
예제 출력 4 복사
14
출처
알고리즘 분류
3. 나의 풀이
문제 이해 및 접근
이 문제는 양방향 순환 큐를 활용하는 문제로, 주어진 위치의 원소를 큐에서 꺼낼 때 최소한의 이동 횟수로 원소를 뽑아내는 것이 목표입니다. 큐는 덱(deque) 자료 구조를 활용하여 양쪽에서 자유롭게 원소를 추가하거나 제거할 수 있으며, rotate() 메서드를 통해 왼쪽 또는 오른쪽으로 회전할 수 있습니다.
큐에서 원소를 꺼낼 때, 가능한 3가지 연산 중 2번(왼쪽 회전)과 3번(오른쪽 회전)의 횟수를 최소화하는 것이 중요합니다.
접근 방법
- 첫 번째 원소를 뽑아내기:
- 이 연산은 문제가 되지 않으며, 언제나 수행할 수 있습니다.
- 왼쪽으로 한 칸 이동:
- 뽑아내려는 원소가 큐의 앞쪽에 가까이 있을 때 사용합니다. 원소의 위치가 큐의 길이의 절반보다 앞에 있으면, 왼쪽으로 이동하는 것이 효율적입니다.
- 오른쪽으로 한 칸 이동:
- 뽑아내려는 원소가 큐의 뒤쪽에 가까이 있을 때 사용합니다. 원소의 위치가 큐의 길이의 절반보다 뒤에 있으면, 오른쪽으로 이동하는 것이 효율적입니다.
해결 과정
- 주어진 큐를 생성하고, 뽑아내려는 원소의 위치를 저장합니다. 여기서 큐의 값은 뽑아내는 위치에 해당하는 값이 들어가야 합니다. 그렇기 때문에 1부터 N까지의 숫자를 저장합니다.
- 각 원소를 순서대로 처리하면서, 그 원소를 뽑아내기 위한 최소 이동 횟수를 계산합니다.
- 뽑아내려는 원소의 위치가 큐의 앞쪽에 가까운지, 뒤쪽에 가까운지에 따라
rotate()메서드를 사용하여 큐를 회전시킵니다.
- 뽑아내려는 원소의 위치가 큐의 앞쪽에 가까운지, 뒤쪽에 가까운지에 따라
- 각 원소를 뽑을 때 필요한 회전 횟수를 모두 합산하여 결과로 출력합니다.
코드 설명
import sys
from collections import deque
# 입력 받기
N, M = map(int, sys.stdin.readline().split())
queue = deque([i + 1 for i in range(N)]) # 1부터 N까지의 숫자를 큐에 저장
position = list(map(int, sys.stdin.readline().split())) # 뽑아내려는 숫자들의 리스트
cnt = 0 # 회전 연산 횟수를 저장할 변수
for i in position:
while True:
if queue[0] == i:
queue.popleft() # 첫 번째 원소가 목표하는 값일 때, 그냥 꺼냄
break
else:
# 왼쪽 회전이 더 효율적인 경우
if queue.index(i) <= len(queue) // 2:
while queue[0] != i:
queue.rotate(-1) # 왼쪽으로 한 칸 회전
cnt += 1
# 오른쪽 회전이 더 효율적인 경우
else:
while queue[0] != i:
queue.rotate(1) # 오른쪽으로 한 칸 회전
cnt += 1
# 결과 출력
print(cnt)
코드 설명
- 입력 처리:
- 첫 번째 줄에서 큐의 크기
N과 뽑아낼 원소의 개수M을 입력받습니다. - 두 번째 줄에서 뽑아낼 원소들의 위치를 리스트로 저장합니다.
- 큐는 1부터 N까지의 숫자를 가진 양방향 순환 큐로 설정됩니다.
- 첫 번째 줄에서 큐의 크기
- 회전 처리:
- 각 원소를 순서대로 뽑아내기 위해 반복문을 실행합니다.
- 현재 큐의 첫 번째 원소가 우리가 찾는 값이면,
popleft()로 큐에서 제거합니다. - 그렇지 않다면, 원소의 현재 위치를 기준으로 큐의 앞쪽 또는 뒤쪽으로 이동하는 것이 더 효율적인지 계산한 후,
rotate()메서드로 왼쪽 또는 오른쪽으로 회전시킵니다.
- 결과 출력:
- 모든 원소를 처리한 후, 회전 횟수
cnt를 출력합니다.
- 모든 원소를 처리한 후, 회전 횟수
시간 복잡도
이 문제에서 큐의 크기 N은 최대 50이므로, 각 회전 연산은 최대 50번의 연산을 필요로 합니다. M개의 원소를 처리하므로, 최악의 경우에도 시간 복잡도는 , 즉 입니다. 이 시간 복잡도는 문제의 제한 내에서 충분히 해결 가능합니다.
마무리
이번 문제는 덱(deque) 자료 구조의 핵심 기능인 양방향 회전을 활용하는 문제로, 효율적인 연산을 통해 큐의 원소를 뽑아내는 과정에서 최소한의 연산 횟수를 요구했습니다. 특히, rotate() 메서드를 사용하여 큐를 왼쪽 또는 오른쪽으로 회전시키는 방법을 통해 문제를 해결할 수 있었으며, 이를 통해 덱의 장점을 실감할 수 있었습니다.
이번 풀이를 통해 덱의 활용법과 더불어, 어떻게 하면 효율적인 알고리즘을 설계할 수 있는지에 대한 감각을 익힐 수 있었습니다. 평소에 스택이나 큐 문제를 풀때도 collections모듈의 deque 클래스를 적극적으로 활용했는데, 이번 문제는 완전히 덱 자료 구조 자체를 활용하는 문제여서 신선했습니다.
다음에 또 다른 문제로 찾아오겠습니다.
Keep Going!! ⭐
