백준 1021번: 회전하는 큐 (Python)

https://www.acmicpc.net/problem/1021

1021번: 회전하는 큐

---

Level: Silver III

Solved By: Deque

📄 Deque

양방향에서 push와 pop이 가능하도록 해야 합니다. 즉, 덱(Deque)을 사용하기 위해 파이썬에서는 아래와 같이 불러와줍니다.

from collections import deque

파이썬의 deque은 아래와 같이 사용 가능하며, 인덱싱이 가능하다는 것을 인지하고 있으면 좋습니다. 인덱싱이 가능할 거면 list를 사용하면 되는 거 아닌가 싶지만 인덱싱과 추가, 삭제 연산에 있어 서로 다른 시간 복잡도를 가지기 때문에 이 점을 알고 있다면, 상황에 맞게 유연하게 알맞은 Data Sturcture를 사용하면 될 거 같습니다.

[Indexing]

- List: O(1)로 원소에 빠르게 접근

- Deque: 반복적으로 접근을 해야 해서 O(n)이라는 선형적인 시간 소요

[Push/Pop]

- List: 맨 끝에 push/pop은 O(1) 소요, 앞에 원소를 push/pop 하는 것은 모든 원소를 옮겨야 하기 때문에 O(n)

- Deque: 양 쪽 모두 O(1)

dq.appendleft(value) # front push
dq.popleft() # front pop, front value return
dq.append(value) # end push
dq.pop() # end pop, end value return

📄 깊은 복사

문제를 풀다가 막히는 부분이 있었는데 C++과 다르게 Python에는 Mutable, Imutable이라는 개념이 있습니다.

Mutable은 어떤 변수에 대해 복사하여 새로운 변수를 할당해도 새로운 변수를 할당하면, 기존의 변수까지 변하는 객체들을 말합니다. 즉, 같은 메모리 주소를 공유한다는 것입니다.

Immutable은 반대로 새로운 변수를 할당하였을 때, 각기 다른 메모리 주소를 가지는 객체를 말합니다.

이러한 Mutable은 list, set, dictionary 같은 데이터가 있고, 나머지 int, string, float 등의 데이터는 모두 Immutable입니다.

 

그래서 Mutable을 사용할 때, 논리적 오류가 발생하지 않도록 깊은 복사(Deep Copy)와 얕은 복사(Shallow Copy)라는 개념이 존재합니다.

얕은 복사(Shallow Copy)란 위에서 말한 Mutable의 특성 그대로 메모리 주소 값을 참조하는 복사이고,

깊은 복사(Deep Copy)란 객체 그 자체를 복사하여 메모리 주소 값을 공유하지 않는 복사를 의미합니다.

문제를 풀 때, 필요한 것은 깊은 복사였으며 파이썬의 copy 모듈을 통해 아래와 같이 깊은 복사를 할 수 있습니다.

num_ = copy.deepcopy(num)

📄 Call By Reference

C++에 적응되어 있다 보니 함수를 Call 할 때, list(Mutable)를 함수에 넘겼더니 의도치 않은 변형이 일어났었습니다. 

Call-By-Value에 적응되어 있었는데 파이썬은 Mutable / Immutable에 따라 Call-By-Value / Call-By-Reference가 달라집니다.

+ Call-By-Reference를 막기 위해 깊은 복사를 사용했었습니다.

📄 Conclusion

• Deque의 사용법
• Python의 Mutable (Call-By-Reference) / Immutable (Call-By-Value)
• Deep Copy / Shallow Copy

from collections import deque
import copy

n, m = map(int, input().split())
num = deque([i for i in range(1, n+1)])
order = list(map(int, input().split()))


def check_left(idx, temp):
    cnt = 0
    while True:
        #print('left debug')
        if temp[0] == idx:
            temp.popleft()  # 1st operation
            return cnt, temp
        a = temp.popleft()
        temp.append(a)
        cnt += 1


def check_right(idx, temp):
    cnt = 0
    while True:
        #print('right debug')
        if temp[0] == idx:
            temp.popleft()  # 1st operation
            return cnt, temp
        a = temp.pop()
        temp.appendleft(a)
        cnt += 1


result = 0

for findIdx in order:
    num_temp1 = copy.deepcopy(num)  # Call by object reference, 원본 변수 변함 방지
    num_temp2 = copy.deepcopy(num)

    #print(f'Left num deque {num_temp1}')
    cnt_left, num_left = check_left(findIdx, num_temp1)

    #print(f'Right num deque {num_temp2}')
    cnt_right, num_right = check_right(findIdx, num_temp2)

    #print(min(cnt_left, cnt_right))
    if cnt_left < cnt_right:
        result += cnt_left
        num = num_left
        #print(num_left)
    else:
        result += cnt_right
        num = num_right
        #print(num_right)

print(result)