[프로그래머스] [Python] Level2_프린터

https://programmers.co.kr/learn/courses/30/lessons/42587

코딩테스트 연습 - 프린터

dequeue를 사용하는 문제

++ 2021.10.01

 

답안 코드는 저번에 푼 것과 동일하다.

그러나 이번에는 정말 안보고 혼자 풀었는데 또 안풀려서 고민했던 지점과 새로 배운 점을 기록하고자 한다.

 

1. deque 사용

python에서 queue 자료형 사용 시 deque를 무족권 import해서 쓰라는 것은 본적이 있다.

앞으로 deque import하는 법과 선언법을 익혀 둬야겠다.

from collections import deque

def solution(priorities, location):
	dq = deque([(v,i) for i, v in enumerate(priorities)])
    print(dq)

#priorities [2, 1, 3, 2]
#deque([(1, 0), (1, 1), (9, 2), (1, 3), (1, 4), (1, 5)])

 

2. enumerate 사용

출처 : python 공식 문서

처음 dictionary나 queue를 선언할 때 좋은 메소드이다.

사용법을 알아두자!

index와 함께 foreach를 돈다.

 

3. max함수 사용

    while(queue):
        doc = queue.pop(0)
        for i in range(len(queue)):
            if queue and queue[i][1]>doc[1]: #들어가
                queue.append(doc)
                break
            else:
                cnt += 1
                if doc[0]==location:
                    print(doc, cnt)

 

헤매다가 결국 버린 구현 방식이다.

for문을 돌면서 max값인지 아닌지를 확인하는데, 문제는 for문을 돌리면서 적절한 break와 함께 최종 인쇄되는 시점에 cnt를 더해주고 해야하는데 그 시점을 잡지 못했다.

결국 순서가 더해짐에 따라 priorities의 문서가 어떤 순서로 변화하는지 까지는 잡았는데 cnt를 못잡아서 포기했다.

 

복잡해진 원인은 max값을 찾기 위한 for문이었던 듯하다.

저번에 확인한 답안코드를 보니, max함수로 그냥 max값을 가져온다.

그래서 처음에 deque 초기화 할 때, tuple에 (index, value)순서가 아닌 (value, index)순서로 넣는다.

print를 찍어 확인해보니, tuple의 앞에 오는 값 기준으로  max함수를 돌리고,

그렇다면 value기준의 max값이 궁금한 것이기에 (value, index)의 형식으로 deque에 넣는 것이 맞는 로직이다.

 

추가로 list에 들어간 tuple의 max값을 구하는 다른 방법이 있어 첨부한다.

lis=[(101, 153), (255, 827), (361, 961)]

max(lis,key=lambda item:item[1])
#(361, 961)

max(lis,key=lambda item:item[1])[0]
#361

 

https://stackoverflow.com/questions/13145368/find-the-maximum-value-in-a-list-of-tuples-in-python

위 링크가 출처인데, 출처로 가면 itemgetter()와 timeit를 사용하는 방법도 있지만 모르는 것이니 생략...

---

+ 2021.09

 

from collections import deque

def solution(priorities, location):
    
    dq = deque([(v, i) for i, v in enumerate(priorities)]) #dequeue
    #v:값, i:인덱스
    cnt = 0
    
    while(dq):
        pop = dq.popleft()
        if dq and pop[0]<max(dq)[0]: #기다려
            dq.append(pop)
        else: #탈출
            cnt += 1
            if pop[1] == location: #찾았을 때
                break
    return cnt

---

1차 시도 - Fail

list를 사용하고 싶었고, 몇 번 인쇄하는지(cnt)와 location의 상관관계를 구하고 싶었는데...실패했다

그리고 왠지 모르겠지만 len(priorities)에서 자꾸 Nontype은 len이 없다고 TypeError가 나서 포기...ㅠㅜㅠ

def solution(priorities, location):
    cnt = 0 #번째로 인쇄
    
    while len(priorities):
        if priorities[0] > max(priorities):
            priorities.pop(0)
            cnt += 1
            if cnt == location : 
                return cnt
        else:
            priorities = priorities[1:].append(priorities[0])

다른 사람 풀이에서 내가 원래 하고싶었던  location를 update하는 코드를 찾았다!!!

(프로그래머스 > 다른사람풀이 에서 변수만 내가 알아보기 쉽게 바꿈)

def solution(priorities, location):
    ans = 0
    max = max(priorities)
    while True:
        current = priorities.pop(0)
        if max == current: ##인쇄##
            ans += 1 #번째인쇄
            if location == 0:
                break #인쇄는 무조건 조건이 맞을 때 이뤄지며 그때 target의 위치는 0일수밖에
            else:
                location -= 1 #앞에 꺼가 인쇄되었으니 하나 땡긴다
            max = max(priorities) #pop 이후 max값 update
        else:  ##순서변경##
            priorities.append(current)
            if location == 0:
                location = len(priorities)-1
            else:
                location -= 1
    return ans

2차 시도 - Fail

def solution(priorities, location):
    dq = [(v, i) for i, v in enumerate(priorities)] #tuple
    cnt = 0 #번째로 인쇄
    
    while len(dq):
        item = dq.pop(0)
        if item[0] < max(dq)[0]: #아직탈출X
            dq.append(item)
        else: #인쇄
            cnt += 1 #번째로 인쇄
            if item[1] == location:
                break
    return cnt

처음 주어진 테스트케이스 2개는 통과했는데 제출하면 죄다 런타임 에러가남..ㅠㅜㅠㅜㅠ

그리고 dq에 넣을 때 (index, value) 튜플로 넣었었는데 max가 제대로 안먹었다.

Tuple의 정렬이나 max값은 [0]번째 값을 기준으로 하나보다.

결국 dequeue로 다 변경

3차 시도

from collections import deque

def solution(priorities, location):
    dq = deque([(v, i) for i, v in enumerate(priorities)]) #dequeue
    cnt = 0 #번째로 인쇄
    
    while len(dq):
        item = dq.popleft()
        if dq and item[0] < max(dq)[0]: #아직탈출X
            dq.append(item)
        else: #탈출O
            cnt += 1 #번째로 인쇄
            if item[1] == location:
                break
    return cnt

 

괜히 if절 조건 한번 바꿔봄...

코테 때 푼다면 탈출 못하는 경우를 찾는 것보다 탈출하는 경우를 잡는게 나을 수도 있겠다는 생각이 듦

(ex. list 길이가 0이 된다거나 등등 검사하기 애매한 케이스)

from collections import deque

def solution(priorities, location):
    
    dq = deque([(v, i) for i, v in enumerate(priorities)]) #dequeue
    cnt = 0
    
    while len(dq):
        item = dq.popleft()
        if len(dq) == 0 or item[0] >= max(dq)[0]: #탈출O
            cnt += 1 #번째로 인쇄
            if item[1] == location:
                break
        else: #아직탈출X
            dq.append(item)
            
    return cnt

 

💡최종로직

0. dequeue 선언

1. dq가 있을 때

  1-1. dq에 pop이후 값이 있고 뒤에 남은 값중 max값이 있을 때, 뒤에 갖다 붙인다.

  1-2. dq에 pop이후 값이 없고 탈출 조건에 맞지 않을 때, 인쇄한다

    1-2-1. pop한 값의 index가 주어진 location과 같다면, break

2. 몇번 인쇄했는지 세는 cnt를 return

 

 

1. 맨앞에서 pop, 맨뒤에서 append는 dequeue. List로도 가능은 하지만 dequeue가 복잡도 측면에서 더 좋다

2. 뭔가 테스트케이스가 안맞는다면 리스트에 값이 없거나, 하나 남는 테스트케이스를 생각해볼 것