[python] 백준 알고리즘 1966번 프린터 큐, 튜플 사용없는 풀이

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

1966번: 프린터 큐

T = int(input())
for _ in range(T):
    N, M = map(int, input().split())
    q = list(map(int, input().split()))
    ck = [False]*N  # target 번호 추적 체크 리스트
    ck[M] = True  # target만 True로 변환
    cnt = 0
    target = q[M]
    idx_t = M

    def down_shift(idx):
        ck = [False] * len(q)
        idx -= 1
        ck[idx] = True
        return idx, ck

    def back_shift(idx):
        ck = [False] * len(q)
        idx = len(q) - 1
        ck[idx] = True
        return idx, ck

    while True:
        vip = max(q)
        if q[0] == vip:
            q.pop(0)
            cnt += 1
            if vip == target and ck[0]:
                print(cnt)
                break
            idx_t, ck = down_shift(idx_t)

        else:
            if q[0] == target and ck[0] and q[0] != vip:
                tmp = q.pop(0)
                q.append(tmp)
                idx_t, ck = back_shift(idx_t)

            else:
                temp = q.pop(0)
                q.append(temp)
                idx_t, ck = down_shift(idx_t)

입력 예제

3
1 0
5
4 2
1 2 3 4
6 0
1 1 9 1 1 1

출력 예제

1
2
5

튜플 없이 풀게 되면

상당히 어려워지게 된다.

특히나 테스트케이스 3번의 경우 ([1,1,9,1,1,1])

동일한 숫자들이 있어서 번호를 특정할 수가 없게된다.

이 경우 대부분 check 리스트를 사용하게되고, 

다이나믹 프로그래밍이라 부르는 알고리즘을 사용하게 된다.

q 리스트가 가변적으로 변하기에 함수를 각각 적용하여 풀게되면

튜플을 이용한것보다 비효율적이고, 시간도 많이 걸리게 된다.

가급적 튜플을 적용한 풀이법을 추천드린다.