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

printerqueue.out

0.00MB

printerqueue.in

0.01MB

위 두 파일은 테스트케이스 예제와 결과값이다.

둘다 txt형식으로 열어주면 된다.

 

이 문제를 방금 풀었는데 대략 한시간 좀 넘게 걸린듯하다.

어이가 없게도 검증과정에서 넣은 print문구 하나때문에 이거 잡느라 시간이 꽤 걸렸다.

 

 

풀이::

간단하게 말해서

---

테스트케이스 i

문서개수n, m번째 문서

우선순위 p

---

입력 예시는 이러하다. 

예제 입력을 바탕으로 조금 더 풀자면, 

3  # 테스트 케이스 수
1 0 # 문서의 수 / 몇번째문서?
5 # 우선순위 처음부터 끝까지
4 2
1 2 3 4
6 0
1 1 9 1 1 1

이해가 안되면 말로푸는게 최고다.
첫번째줄부터,
3개의 테스트케이스를 입력받을것이다.
문서의 수는 1개이고 0번째 문서가 몇번째로 출력되는지 찾을것이다.
우선순위는 5이다.
답이 1
문서의 수는 4개이고 2번째 문서가 몇번째로 출력되는지 찾을것이다.
우선순위는 앞부터 1,2,3,4이다.
문서의 수는 6개이고 0번째 문서가 몇번째로 출력되는지 찾을것이다.
우선순위는 앞부터 1,1,9,1,1,1이다.

여기서 우리가 생각해야할건, 지금 우리가 푸는 문제는 Queue라는 것이다.

두번째부터 보자면, 4개의 문서가 있다.

[1,2,3,4]의 우선순위를 가지는 4개의 문서다. 우린 여기서 2번째 인덱스, 즉 3번째 문서가 몇번째로 출력되는가를 찾아야한다.

출력 우선순위는 잠깐만 생각해봐도 높은순서라는걸 알 수 있다.

맨 뒤부터 거꾸로 순서가 될것이다. 때문에, 우린 2번인덱스인 3의 우선순위를 가지는 문서는 2번째로 나온다는걸 알 수 있다.

 

세번째는 [1,1,9,1,1,1]의 우선순위를 가지는 6개의 문서가 있고 0번째 문서가 몇번째로 나오는가?를 찾아야한다.

일단 눈으로 보면 2번인덱스가 첫번째이다.

그리고 0번인덱스가 두번째인걸로 보일수도 있는데, 우린 큐를 푸는중이다.

다음 인덱스의 우선순위는 1이다. 그 뒤로 계속 검증하다가 끝에 다다르면 검산안한 앞까지 검사해서 가장 높은수를 빼주는건데, 여기서 수가 모두 같기때문에, 단순히 9 다음에 오는 1부터 즉 3번째 인덱스부터 차례대로 출력되는걸 알 수 있다.

 

한마디로 인덱스 출력 순서는 2 - 3 - 4 - 5 - 0 - 1이고 우리가 찾는 0번인덱스는 5번째에 있으므로 5가 나온다.

 

첫 시도는 remove로 값을 날려줬는데 뭔가 애매했다. 2 - 2 - 2이런식으로 나온다. 때문에 우선순위 리스트를 복사해서 의미상 리스트를 둔 후 개수는 거기서 세는걸로 했다.

 

조금 더 쉽게 풀어보자. 총 6개의 문서가 있고, 2번인덱스를 출력했다. 그럼 다음부턴 1개가 줄어서 우린 5번만 검사해도 전부 검사한 꼴이 된다. 하지만 그렇다고 remove를 해주면 인덱스가 제대로 안찍힌다. 물론 이 경우 다른식으로 처리하면 되지만, 내 경우 약간의 잔머리를 추가했다.

 

우선순위가 높은점을 이용해서, 일단 2번인덱스의 9값을 0으로 바꾸어줬다. 그리고 우선순위리스트를 복사한 또 다른 리스트에서 해당 9를 remove해줘서 수를 줄였다. 이 길이를 매번 len으로 재준후 for문을 사용하면된다.

 

그러면 처음엔 6번돌던 for문이 5번돌고 4번돌고 이런식으로 반복한다.

 

물론 이 방식을 사용하려면 반복문이 2중이어야한다.

 

내 경우 잔머리를 추가로 쓴게 최대 값을 지정해서 중간에 만족하면 중단하고 다음수로 넘어가게 했다.

예로들어 

100 32

2 9 2 4 1 8 8 5 4 6 3 4 6 2 8 2 3 6 6 2 2 8 2 5 8 9 6 2 6 1 2 8 1 4 9 8 2 5 3 3 1 3 4 6 5 1 7 5 6 1 4 6 6 5 1 5 3 6 4

8 7 6 4 5 7 3 1 6 8 2 7 6 4 8 3 8 8 7 1 5 6 5 8 2 9 8 4 2 3 8 8 7 4 2 9 8 5 9 2 1

 

우선순위는 1~9까지이고 1번째 인덱스인 9라는 값은 우선순위 최대값인 9와 같다.

그러면 굳이 뒤를 안돌아도 된다.

이런식으로 쭉 돌게한다. 언젠가 9가 없다면 우선순위 최대값을 1을 깎아준다는 개념으로 접근했다.

이러면 굳이 n^2로 돌지 않아도 된다.

 

공유된 테스트 케이스 in / out을 올려놓았다. 메모장으로 열면 된다.

내가 처음 막힌 부분은 저 위에 예시이다. 32번문서가 몇번째로 출력이 되는가?였는데

자꾸 94라는 값이 나온다. 100이라는 값이 나와야한다.

 

이때 단순하게 계산해주면된다.

9라는 값을 다 훑고 난 이후는 마지막에 나오는 9다. 그럼 우린 어떠한 값의 시작과 끝을 보면 된다.

9의 경우 2번째에서 시작하고 98번째에서 끝난다. 그럼 98번부터 8을 찾으면 된다. 그러면 96번째 8이 마지막이 될것이고, 이걸 반복하면 위에 빨강/파랑으로 색칠된 구간이 있는데, 실제로 카운트해보면 빨간색 6에서 끝난다.

그러면 당연히 5라는 값의 시작은 파란색 5부분이다. 그리고 빨간색 6 바로 전에 있는 5가 끝나는 곳이다.

이걸 계속해서 반복하면 우리가 찾는 32번째 수는 1이고 얘는 1의 마지막 값이라는걸 알 수 있다.

 

자 이제 우린 머릿속에서 검증을 끝냈다.

 

그럼 코드로 풀어내면 된다.

 

위 얘기를 요약해보면, 처음시작때 0번 인덱스를 가르키는 변수를 지정해주고, 해당 맥스값(예:9)이 끝나는 구간이 바로 다음 맥스값(예:8)이 시작되는 구간이다. 그럼 우린 for문을 다시 들어갈때 시작값을 맥스값(여기서 9가 끝난 구간의 인덱스 값)을 주면 된다. 위 예제의 경우 98이라는 값이 들어가있다.  이대로하면 인덱스 범위 초과가 일어난다.

(for문의 i라는 변수는 의미가 없는 애다.) 

 

생각해보자 9라는 값이 6개가 나왔다치면, 8을 셀땐 100-6인 94번을 돌아야한다.

우린 시작을 98로 할것이다. 그러면 단순하고 98+94를 해주면 된다. 98 ~ 192까지 돌것이고 결국 94번을 돈꼴이다.

그래서 난 우선순위가 저장된 리스트를 복사한 다른 리스트를 둔것이다.

 

이를 반복하면 된다. 숫자를 써놓고 펜을 들어 기계의 바늘이 데이터를 가리키는것처럼 하나하나 진행한다고 생각하면 된다.

 

물론 지금은 내가 어느정도 정리를 한 이후에 기술했기때문에 다소 정렬되었지만, 내 코드는 맛있는 스파게티 그 자체다.

 

아무튼 코드주의

모든 문제가 그러하듯, 가급적 남의 코드는 안보는게 좋다. 최소 3시간을 투자해서 개념조차 안나온다면 보고, 개념은 나온다면 안보는게 좋다.

 

코 드 주 의

 

 

 

 

 

 

스파게티 스파게티 맛있는 스파게티

 

 

 

 

 

 

 

#1966 printer Queue

import sys

def checkPriority(queue,m): # 6 / 17 / 6 / 15 / 11 / 11 / 9 / 15 / 10
    returnIndex = list()
    maxIndex = 0
    comp = queue[:]
    priorNum = 9
    while True:
        if len(comp) < 1:
            return returnIndex
        data = maxIndex
        for i in range(maxIndex,maxIndex + len(queue)):
            if queue[maxIndex] == priorNum:
                break
            if data + 1  == len(queue):
                data = -1
            data+=1
            if queue[maxIndex] < queue[data]:
                maxIndex = data
        if queue[maxIndex] < priorNum:
            priorNum = queue[maxIndex]
        returnIndex.append(maxIndex)
        comp.remove(queue[maxIndex])
        queue[maxIndex] = 0
        maxIndex += 1
        if maxIndex >= len(queue):
            maxIndex = 0
        

def main():
    nInput = int(sys.stdin.readline())

    for i in range(nInput):
        n,m = map(int,sys.stdin.readline().split())
        priorities = list(map(int,sys.stdin.readline().split()))
        queue = [0 for j in range(n)]
        for j in range(n):
            queue[j] = priorities[j]
        result = checkPriority(queue,m)
        # m번째 인덱스가 몇번째 queue인가?
        for k in range(len(result)):
            if result[k] == m:
                print(k + 1)
                break

main()