deque를 rotate하고 popleft하며 문제를 해결하는 과정에서, 다음과 같은 에러가 발생하였다.
RuntimeError: deque mutated during iteration
이러한 에러는 deque를 순회하는 반복문 내에서 deque의 요소가 변경되거나 사이즈가 변경될 때 발생한다.
이를 해결하기 위해서는 list를 새로 만들어 복제하거나, copy 모듈을 사용한다. 나는 후자의 방법을 채택하였다. copy 모듈을 import한 뒤 deepcopy 메소드를 사용하여 에러를 해결하였다. 작성한 파이썬 코드는 다음과 같다.
import sys, copy
from collections import deque
tc=int(sys.stdin.readline())
for i in range(tc):
N,order=map(int,sys.stdin.readline().split())
num=list(map(int,sys.stdin.readline().split()))
priority=[[] for _ in range(N)]
for i in range(N):
priority[i]=[i,num[i]]
answer=[]
priority=deque(priority)
while copy.deepcopy(priority):
for j in copy.deepcopy(priority):
if j[1]!=max(num):
priority.rotate(-1)
else:
answer.append(priority.popleft())
num.remove(j[1])
for k in range(N):
if answer[k][0]==order:
print(k+1)
원본배열을 보존하기 위해 배열을 복사해야 하는 경우가 발생한다. 객체를 무작정 복사해서 사용하면 원본 객체가 핸들링되어 데이터가 변경되어서 큰 문제를 야기할 수 있기 때문에 객체를 복사할 때에는 주의해서 다뤄야 한다.
객체를 복사하기 전에 먼저 객체의 특징 중 Mutable과 Immutable의 의미에 대해 알 필요가 있다.
파이썬에서 변수는 자신에게 대입된 객체를 가리키는 일종의 포인터 같은 존재이다. 때문에 파이썬에서 변수는 자체 저장공간을 할당받지 않으며 객체를 가리키는 개념이다.
a=1에 대해, 파이썬에서는 a와 1은 별개의 존재다.
a라는 변수는 Integer 1이라는 객체를 가리키고 있을 뿐 a의 변수에 정수 1의 값이 할당 된 것이 아니다.
Mutable과 Immutable의 개념은 여기서 적용된다.
Mutable='변한다', Immutable='변하지 않는다'
개념을 쉽게 이해하기 위해 다음과 같은 예시를 살펴보자.
a = 1
b = a
print(a, b) # 1 1
위 구문에서 a와 b는 동일하게 (정수 1) 이라는 객체를 가리키게 된다.
여기서 b의 값을 2로 바꾸면
a = 1
b = a
print(a, b) # 1 1
b = 2
print(a, b) # 1 2
예상한 것과 마찬가지로 위의 결과가 출력된다. a의 값은 수정되지 않았다.
이는 int의 자료형이 Immutable한 특징을 가졌기 때문에 그렇다. immutable한 객체는 생성이 된 후 값 수정이 불가능하다.
Mutable한 객체에는 대표적으로 list가 있다.
a = [1, 2, 3, 4]
b = a
print(a, b) # [1, 2, 3, 4] [1, 2, 3, 4]
위 코드에서 리스트 b의 요소를 변경하면
a = [1, 2, 3, 4]
b = a
print(a, b) # [1, 2, 3, 4] [1, 2, 3, 4]
b[1] = 0 # 배열 b의 두번째 값을 0으로 바꿔준다.
print(a, b) # [1, 0, 3, 4] [1, 0, 3, 4]
첫 번째 예시에서의 결과와는 다르게 원본 배열 a의 값도 바뀌었다.
이는 리스트가 Mutable한 특징을 가졌기에 원본배열의 값이 바뀐 것이다.
+) 리스트 수정의 예시에서 a와 b는 같은 주소값을 참조한다. 그런데 list는 Mutable 하기 때문에 b의 값이 변경되면 해당 주소값에 있는 값이 변경되기 때문에 같은 주소값을 참조하던 a도 바뀐 값을 반환하는 것이다.
a = 1
b = a
print(id(a), id(b)) # id() 로 객체가 어떤 주소값(레퍼런스)를 확인하는지 알 수 있다.
print(a is b) # True. is는 아이디 연산자로 객체가 같은 id값을 가지는지 T/F 를 반환한다.
c = [1, 2, 3, 4]
d = c
print(id(c), id(d))
print(c is d) # True
위 구문에서 a와 b, c와 d는 각각 동일한 레퍼런스(주소값)를 참조하고 있다.
하지만 아까와 같은 방식으로 b와 d의 값을 바꿔보자.
b = 0
d[1] = 0
print(id(a), id(b))
print(a is b) # False
print(id(c), id(d))
print(c is d) # True
Integer형 변수는 Immutable 하므로 값이 바뀔 수 없어 다른 주소 id값을 가지지만, list형 변수는 Mutable하므로 값이 바뀌고 여전히 같은 주소값을 참조한다.
위의 예제를 통해 리스트들은 모두 얕은 복사를 통해 주소값만 복사되어서 복사된 객체에서 값을 바꾸었던 것이 Mutable한 list의 특성때문에 원본 객체의 값도 바뀐 것을 확인하였다.
하지만 원본 배열을 보존해야 하는 경우가 발생하고, 이러한 경우에는 배열을 '깊은 복사' 하여야 한다.
import copy
a = [1, 2, 3, 4]
b = copy.deepcopy(a)
b[1] = 0
print(a, b) # [1, 2, 3, 4] [1, 0, 3, 4]
a = [1, 2, 3, 4]
b = a.copy()
b[1] = 0
print(a,b) # [1, 2, 3, 4] [1, 0, 3, 4]
a = [1, 2, 3, 4]
b = list(a)
b[1] = 0
print(a,b) # [1, 2, 3, 4] [1, 0, 3, 4]
a = [1, 2, 3, 4]
b = []
b.extend(a)
b[1] = 0
print(a,b) # [1, 2, 3, 4] [1, 0, 3, 4]
a = [1, 2, 3, 4]
b = a[:]
b[1] = 0
print(a,b) # [1, 2, 3, 4] [1, 0, 3, 4]
a = [1, 2, 3, 4]
b = [i for i in a]
b[1] = 0
print(a,b) # [1, 2, 3, 4] [1, 0, 3, 4]
a = [1, 2, 3, 4]
b = []
for i in range(len(a)):
b.append(a[i])
b[1] = 0
print(a,b) # [1, 2, 3, 4] [1, 0, 3, 4]
a = [1, 2, 3, 4]
b = []
for item in a:
b.append(item)
b[1] = 0
print(a,b) # [1, 2, 3, 4] [1, 0, 3, 4]
참고문헌
https://crackerjacks.tistory.com/14
https://wikidocs.net/16038
https://dobbycantype.tistory.com/15