[백준::1966 python3] 프린터 큐

23일엔가.. 21일엔가.. 아무튼 간만에 본가로 올라와서 하루도 안쉬고 사람들 만나면서 놀다가 지금 동탄역에서 기차 기다리는중.. 프린터큐가 생각나서 적어본다

 

오늘은 짧고 굵게

 

아는 동생에게 알려주려고 주석달아서 써놓은 코드를 공유한다. 때문에 긴 설명은 없음 (ㄱㅇㄷ)

 

간단하게 적기

1. 복합기 + 큐구조.

2. 입력은 테스트케이스 -> 문서의개수,조회할문서의인덱스 -> 우선순위들

3. 출력은 조회할 문서의 인덱스가 몇번째로 출력되는가?

 

여기서 내 주요 풀이 키워드는 이렇다.

1. 같은 우선순위의 처리 순서

2. 인덱스의 끝에 갔을때?

3. 조회의 수

 

일주일정도 된거같은데 가물가물..해서 이정도만.. 자세한건 코드 맨 하단의 주석을 보길 바란다.

 

우선 1. 같은 우선순위의 처리 순서란, 1 1 9 1 1 1일때 처리 순서인데, 이건 맨 앞이 아닌 현재 인덱스의 위치로부터 뒤에있는 애들 중 가까운 애들이다. 그래서 해당 예제는 5인가 나왔던걸로 기억한다.

 

그리고 출력은 인덱스 번지가 아닌 몇번째인지 알아내야하기때문에 +1을 해야한다.

 

음 그리고 덧붙이자면 100개의 문서가 있고 각기 다른 우선순위일때 어떻게 거르는가를 생각해야하는데,

당장 생각난건 두가지였지만 난 단순히 최대 우선순위 값인 9부터 전부 싹 찾아서 새로운 리스트에 저장하고 그다음 8..7..이런식으로 돌아가며 싹 저장했다.

 

2. 인덱스의 끝에 갔을떄?  예로들어 100개의 수 중 10개의 9가 나갔고 이제 8이 할 차롄데 현재 인덱스가 99번째라면, 바로 indexError가 나는데, 이 경우 for i in range(something):에서 i를 가지고 놀지 말고 그냥 index라는 변수를 따로 빼서 걔로 놀면 된다. 그리고 여기서 함정이 있는데 이건 3번에서 설명

 

3. 조회의 수.  이쯤까지 python으로 코딩해서 올라온 사람의 경우 누군가의 코드를 베껴 올라온게 아니라면 알아챘을것이다. 파이썬이 상당히 느리단걸.  "아니 겨우 이런걸로 시간초과가 난다고?" 아니시에이팅

 

그렇다 굉장히 느리다. 게다가 주 언어가 C계열인 난.. 감탄했다. 아무튼 이것도 그냥 머리쓰면 되는데

우선순위가 저장되어 있는 리스트의 우선순위를 remove로 빼면서 다른 리스트에 값을 저장하던가, 아니면 그림자 역할을 할 리스트를 만들어 따로 관리하는것인데

전자의 경우 인덱스가 꼬여버린다. 분명 50번째 인덱스의 9가 첫번째 9인데 remove로 빠져버리는바람에 51번째 인덱스의 두번째 9가 50으로 들어와버린다. 그래서 내 경우 0으로 처리해줬고

그림자역할을 할 인덱스에 그 9를 빼버렸다. 정확히는 먼저 빼고 값을 0으로 바꿔준셈

 

근데 사실 이것도 사용안한걸로 기억한다.

 

아마 내 방식은 maxNum이라고 각 우선순위 최대값을 9부터 내려온다고 했었는데

단순히 그 값이 해당 리스트에 몇개 있는지 세고 그 만큼 반복하라하면 되는것.

그러면 나중에 1000개의 리스트에 1이 단 하나 있다고할때, 최악의 경우 999번을 돌지 않아도 된다.

 

자세한건 밑에 코드를 참고하고 이번역시 코드를 안보는걸 추천한다.

진짜 진심으로 실력 하나도 안늘어요.

import sys
from ezTest import *

def checkPriority(arData:list): # Function Annotation
    # 파이썬의 고질적인 return or parameter 타입 표기의 문제를 완화시켜주는 애
    # arData:list의 뜻은 arData라는 변수가 parameter로 들어오는데, 얘는 list여야한다는뜻
    maxNum = 9 
    breakPoint = len(arData)
    result = list() 
    for i in range(9): 
        if arData.count(maxNum) > 0:
            tryIndex = arData.index(maxNum) 
            break
        else:
            maxNum-=1 
    nextTarget = 0 # 이건 간소화를 위한 코드
    while True:
        if breakPoint == arData.count(0): 
            return result
        if arData.count(maxNum) == 0:                       
            maxNum -= 1
        for i in range(arData.count(maxNum)):
            try:
                nextTarget = arData.index(maxNum,tryIndex)
            except ValueError:
                nextTarget = arData.index(maxNum)
            tryIndex = nextTarget
            if tryIndex >= len(arData):
                tryIndex = 0
            if arData[tryIndex] == maxNum:
                result.append(tryIndex)
                arData[tryIndex] = 0
            tryIndex += 1

def main():
    ez = ezTest()
    values = ez.inFile()

    if ez:
        nInputTestCase = values[0]
        for i in range(1,nInputTestCase,+2):
            queueList = list(map(int,values[i].split()))
            priorities = list(map(int,values[i+1].split()))
            priorList = checkPriority(priorities) # 실질적인 계산하는 함수. 우선순위가 높은대로 리스트에 꽂아줌

            result = priorList.index(queueList[1]) + 1
            print(result)
    else:
        nInputTestCase = int(sys.stdin.readline())
        # 문서의 개수n, 조회할 데이터 순서 m :: 예) 4개의 문서 중 0번째 데이터의 출력순서가 궁금하다
        # 사족을 붙이자면, 프로그래밍은 나비효과 정도로 생각해야함.
        # 첫번째 분기에서 어떤 코드를 짜느냐에 따라 프로그래밍 방식이 달라짐.
        # 다만, 정답이 정해지지 않은건 같음 모든게 정답이자 정답이 아님.
        # 여기서 n,m이라 정의했지만, 어차피 2개의 데이터가 고정적으로 들어오고 n,m쓰기 귀찮아서 리스트로 관리할 생각
        for i in range(nInputTestCase):
            queueList = list(map(int,sys.stdin.readline().split())) # 6 0
            # prioirties
            priorities = list(map(int,sys.stdin.readline().split())) # 1 1 9 1 1 1

            # 여기서도 하나의 분기가 생길수도 있을듯.
            # 6 0 / 1 1 9 1 1 1 의 예제를 볼때, 6개의 문서 중 0번인덱스가 몇번째로 출력되는지를 알고싶은건데, 
            # 우선순위를 for문을 이용해 n개의 데이터의 우선순위를 받느냐, 아니면 상관없이 그냥 받느냐의 차이
            # 참고로 해당 문제는 상관이 없지만, 실제 코딩의 경우 전자로 짜야함

            priorList = checkPriority(priorities) # 실질적인 계산하는 함수. 우선순위가 높은대로 리스트에 꽂아줌

            result = priorList.index(queueList[1]) + 1
            print(result)
        
main()

# 설명
# 코드가 읽는 순서대로 설명할거야.    줄:내용 / 예) 3: 우선순위체크용 함수 -> 3번째 줄 코드는 우선순위체크용 함수라는뜻

# 3: 우선순위체크용 함수
# 4~5: TMI인데 필요한 내용임
# 6: 우선순위변수. 가장 높은 우선순위부터 깎으면서 순위를 넣어줄 예정
# 7: 데이터의 크기를 가지고 있을 변수인데, 이 코드는 혼선 방지를 위해서 해당 값을 빼는게 아닌 0으로 대체해주는 방식을 사용하기에
#   나중에 실제 데이터가 있는 리스트에서 0의 개수를 세고, 원래 있던 데이터의 크기를 비교해서 같다면 모든게 값이 한번씩 변경됐다는 얘기

# 8:우선순위대로 이 리스트에 한꺼번에 저장한 후 결과를 뽑을예정
# 9: index함수는 해당 값이 없으면 valueError가 떠서 그 전에 count를 이용해 조회를 해준 후 있으면 조회하고 없으면 maxNum을 깎을거임
# 10: maxNum값이 리스트에 존재하지 않을경우, 11번 코드를 실행할것
# 11: 10번줄이 참이라면, maxNum이라는 우선순위가 해당 리스트에 존재한다는 뜻이니 바로 index로 위치를 찾아줄것
# 12: 그리고 사용자가 인덱스를 인위적으로 조회하는건 맨 처음뿐이고 이후부턴 알아서 한칸씩 이동하도록, 즉 초기화가 안되도록 해야함
#       그래서 조회되는 즉시 바로 break

# 14: 예로들어 9부터 시작했는데, 9가 없으면 8을 카운트할거고 없으면 또 1을 깎을거임
# 15: 이건 조금 더 빠르게 조회하려고 만든 변수인데
# 예로들어 9,9,9,9,9,9,9,9,9,9,9,9,1,9,9,9,9,9,9,9,9,.... 이런식으로 1000개의 수가 있다고 가정했을때
# 1000번째의 9가 조회 된 이후 중간 어딘가에 있는 1 하나를 제외한 다른 수는 0인데
# 이때 그 1을찾아서 프로그램이 999 * (9-1)번정도 (아마도?) 돌기때문에
# 그런 최악을 면하기 위해 count를 이용해 해당 숫자가 리스트 안에 있는가를 판별한 후
# 없으면 바로 수를 낮추고, 있으면 index로 위치를 바로 찾아내서 거기부터 시작하면 됨

# 17: 총 길이랑 0의 개수가 같다는건 전부 값이 바뀌었다는 뜻
# 18: 해당 테스트케이스의 결과값을 리턴
# 19~20: 이건 9~14에서 쓰인 코드와 같다고 봐도되는데, 다만 9~14는 첫 조회시에만 사용되는반면 해당 코드는 지속적으로 사용됨
# 21: 9부터 시작해서 해당 숫자가 리스트에 몇개 존재하는지만 카운트해서 그만큼만 반복할거임
# 22~25: try except구문인데 우선 count와 index에 대해 간단히 알아야하는데
# count(값)의 경우 값이 존재하지 않으면 0을 리턴해주고, index(값)의 경우 값이 없으면 ValueError를 일으킴
# try except를 안쓸경우 for문 하단에 계속해서 체크해주는애를 넣어야하는데, 그것보다 이정도의 try except구문이 더 효율적임
# index(값,시작인덱스,멈출인덱스) - index함수의 사용법인데, 기본형은 index(값)이렇고 시작,멈출 인덱스를 안넣어주면 해당 리스트의
# 0번지와 끝번지가 자동으로 들어감  우리의 경우 우선순위 값이 내려가더라도 index의 위치는 일정해야하기때문에 
# index(값) 이렇게 넘겨주면 다음 우선순위값의 인덱싱을 할때 맨 처음부터 바라봄. 이러면 index가 계속 초기화 되는거니까
# index(값,시작인덱스)을 설정해서 tryIndex라는 우리가 따로 지정한 최근 조회된 인덱스 위치를 넣어주면 되느것
# 예로들어 60번째 인덱스의 9까지 조회했을때, 8을 조회하려면 8부터 끝번지까지 봐야함
# 단 이 경우 60~끝번지까지 8은 없는데, 시작~59번지 사이에 8이 있을때 index(값,시작인덱스) 이렇게 하면 8 is not in list라는
# ValueError가 뜸. 그래서 이 경우엔 어차피 처음부터 다시 조회하면 보일테니까, index(값) 이렇게만 써줘야함

# 26: 그리고 그 인덱스를 tryIndex에다 넣어줌
# 27~28: 이건 이전코드의 잔재인데 좀 더 쉽게 설명해주려고 새 코드로 풀고 또 그걸 간소화한게 지금코드라서
# 저건 아마도 없어도 될것 같음
# 29: 해당 인덱스의 값이 우리가 현재 조회중인 우선순위값일때, 지금 인덱스 위치를 result 리스트에 넣어주고 현 위치의 값을 0으로 바꾼다.
# 32: 아마 31,32코드도 없어도 될거 같은데.. 이것도 귀찮아서 킵

# 42: queuelist[0] = 문서의 개수, queuelist[1] = 순서를 조회할 문서의 위치
# 44: 우선순위저장 리스트
# 51: 위 함수의 리턴값을 저장할 변수
# 53: priorList에는 중복되지 않는 수가 문서의 개수만큼 들어가있을건데, 
# 예로들어 100개의 문서 중 32번째 문서의 순서가 궁금할때 해당 리스트를 대상으로 index함수를 써서 32를 넣어서 위치를 찾으라고 하면
# 위치가 나올건데 주의할건 인덱스의 시작은 0이기때문에 값을 1만 추가시켜주면 됨.
# 맨 앞에 나올경우 0번째라고 나오는게 아닌 1번째로 나와야하기때문

# 링크 : https://atli-yeondi.tistory.com/99
# 위 링크에 input / output용 테스트케이스 올려놓을거니까 공부하면서 input을 넣고 output을 확인해가면서 어떤게 문제인가 찾아봐!