분류
자료 구조(data_structures), 덱(deque)
문제 설명
지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.
지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.
- 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
- 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
- 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.
큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.
32 6
27 16 30 11 6 23
출력
첫째 줄에 문제의 정답을 출력한다.
59
아이디어
-
구하고자 하는 숫자가 앞쪽에서 가까운지 뒤쪽에서 가까운지 체크해서,
앞쪽과 가까우면 문제의 2번 연산, 맨 앞 원소를 뒤로 보내고 :
rotate(-1)뒤쪽과 가까우면 문제의 3번 연산, 맨 뒤 원소를 앞으로 보내기 :
rotate(1) -
2번 연산을 하게 되면 앞쪽 원소는 하나 감소하고 뒤쪽 원소의 개수는 하나 증가하며, 3번 연산의 경우 반대로 수행됨
-
맨 앞의 숫자와 원하는 숫자가 같을 때는
popleft()한 뒤 해당 숫자 탐색을 멈추기
내 코드1: 비효율적
import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
nums = list(map(int, input().split()))
deq = deque([i for i in range(1, n+1)])
result = 0
for num in nums:
idx = deq.index(num)
front = idx
back = len(deq) - idx
while True:
if deq[0] == num: #
deq.popleft()
break
else:
if front <= back: # 왼쪽 한 칸, 즉 앞에 애들을 뒤로
deq.rotate(-1)
front -= 1
back += 1
else:
deq.rotate(1)
front += 1
back -= 1
result += 1
print(result)-
front랑 back으로 각각 앞쪽 원소 개수, 뒤쪽 원소 개수를 챙겨놓고 한 방에 앞/뒤로 붙이는 방식으로 구현하지 않았음
-
숫자를 pop할 때는 1번 연산으로, 즉 해당 숫자가 맨 앞에 올 때 제거한다고 문제 그대로 받아들여서 굳이굳이 복잡하게 풀게 된 것 같다 ㅜㅜ
-
매번 ... 문제 곧이곧대로 풀으려고 해서 코드가 어색해지는 듯 ..
다른 사람 코드
def f(i,p,q):
if i == m:
return 0
x = q.index(a[i])
y = min((x-p)%len(q), (p-x)%len(q))
q.pop(x)
return y + f(i+1, x, q)
n, m, *a = map(int, open(0).read().split())
q = [*range(1, n+1)]
print(f(0, 0, q))N, M = map(int, input().split())
Q = [*range(1, N+1)]
idx, cnt=0, 0
for i in list(map(int, input().split())):
cnt += min(abs(idx-Q.index(i)), len(Q)-abs(idx-Q.index(i)))
idx = Q.index(i)
del Q[Q.index(i)]
print(cnt)-
[*range(1,N+1)]이나*a처럼*을 잘 활용하게 되면 좋겠음 -
앞쪽에 있는 원소 개수와 뒤쪽에 있는 원소 개수를 비교해서 작은 거를 result에 더함으로써 수행해야 하는 연산의 횟수를 한 번에 계산 가능
-
이 경우 구하려는 원소가 물리적 위치 상으로는 맨 앞에 있는 게 아니지만,
덧셈 연산으로 2번이든 3번이든 연산이 알아서 수행이 된 다음에 맨 앞에 왔다가 pop 되는 것과 같은 효과를 주므로
idx = Q.index(i)로 idx 값을 갱신한 뒤,다음에 구하려는 원소에서는 자신의 위치에서 idx를 뺀 값(내 코드 front와 같은 효과)과 총 길이에서 그만큼을 뺀 값(back과 같은 효과)을 각각 비교하여 작은 것에 대해 동일한 연산을 수행
