[백준 1966번] 프린터 큐 - 큰 수부터 출력하여라

 

-- 처음 짠 코드

import sys

T = int(sys.stdin.readline()) # 테스트케이스의 수

for _ in range(T):
    n, m = map(int, sys.stdin.readline().split()) # 문서의 개수, 알고싶은 문서의 현재 위치
    important = list(map(int, sys.stdin.readline().strip().split()))

    answer_list = []
    while len(answer_list)<n: # 입력받은 문서의 개수만큼 출력될때까지 돌릴거야
        if important[0] == sorted(important,reverse=True)[0]:
            answer_list.append(important[0])
            important.pop(0)
            if m==0:
                print(len(answer_list))
                break
            m -= 1
            if m == -2:  # 찾을 수를 특정해주기 위해 인덱스를 수정해준다
                m = n - 2

        else:
            important.append(important[0])
            important.pop(0)
            m -= 1
            if m== -2: # 찾을 수를 특정해주기 위해 인덱스를 수정해준다
                m = n-2

분명 예제코드도 다 맞고 예상하는 오류들이나 케이스를 다 고려했다고 생각했는데 정답을 제출하면 "틀렸습니다."가 나온다....

코드를 짠 방법은 0번째 인덱스가 가장 큰 값이라면 출력을 해 다른 리스트에 옮겨준다고 생각을 했고 이때 0인덱스를 지워줌 + 찾야할 인덱스 -1을 해주었다. 

 

# 오류 발견 1

100 5

1~10 을 10번 반복해 입력해주니 답이 22가 나왔다 여기서 5인덱스의 값은 6으로 내가 예상하는 답은 10, 9, 8, 7을 모두 10번씩 출력하고 나오는 41이었다. 그런데 왜 22가 나왔을까.. 노트에 필기해보며 생각해 보았다...

 

# 오류 2

8 0

2 4 3 1 2 4 3 1 -> 인덱스가 -2일때 n-2로 바꾸는게 잘못되어 m의 값이 잘못되게된다. 

=> n-2를 len(important) -1로 수정 , 하지만 아직 오류 1은 해결되지 않음

 

-> 프린트를 해 answer_list를 갈때와 그냥 순서를 뒤로 보낼때 구하려는 인덱스의 위치가 달라지는 것을 확인!!!

 

 

-- 정답 코드

 

import sys

T = int(sys.stdin.readline()) # 테스트케이스의 수

for _ in range(T):
    n, m = map(int, sys.stdin.readline().split()) # 문서의 개수, 알고싶은 문서의 현재 위치
    important = list(map(int, sys.stdin.readline().strip().split()))

    answer_list = []
    while len(answer_list)<n: # 입력받은 문서의 개수만큼 출력될때까지 돌릴거야
        if important[0] == sorted(important,reverse=True)[0]:
            answer_list.append(important[0])
            important.pop(0)
            if m==0:
                print(len(answer_list))
                break
            m -= 1
            if m == -2:  # 찾을 수를 특정해주기 위해 인덱스를 수정해준다
                m = len(important)-1

        else:
            important.append(important[0])
            important.pop(0)
            m -= 1
            if m== -2: # 찾을 수를 특정해주기 위해 인덱스를 수정해준다
                m = len(important)-2

sorted에서 가장 큰 숫자와 0인덱스가 같게되어 answer_list로 보내지게 될때에는 뒤로 숫자가 오지 않기때문에 맨 뒤에 있을경우 맨 뒤의 인덱스로 특정해주고, 나머지 위치에서는 크기가 줄기 때문에 숫자가 하나씩 줄어도 상관없다.

하지만 같지 않고 맨 뒤 순서로 보내게 될 때에는 -2인덱스는 뒤에서 2번째인 인덱스이기 때문에 현재 길이의 -2 인덱스 위치로 m을 특정해 주면 된다. 오류해결!!

 

c.f ) 파이썬의 deque(데크)를 사용한 풀이도 있던데 추후에 확인해 공부하도록 하겠다.