[프로그래머스] 스택/큐, 프린터

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

프로그래머스

 

문제 개요

1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다.
2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다.
3. 그렇지 않으면 J를 인쇄합니다.

내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 알고 싶습니다.

(숫자가 클 수록 더 중요한 문서)

 

input
-priorities: 문서의 중요도가 순서대로 담긴 배열
-location: 내가 인쇄를 요청한 문서가 현재 대기목록의 어떤 위치에 있는지.

return
내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지.

 

 

나의 코드

def solution(priorities, location):
  pri_tuple = list(enumerate(priorities))
  target_tup = pri_tuple[location]
  i=0
  while target_tup in pri_tuple:
    (max_idx,max_val) = sorted(pri_tuple, key=lambda x: x[1], reverse=True)[0]
    max_value = (max_idx,max_val)
    if pri_tuple[0][1] != max_val:
      back_lst = pri_tuple[0:pri_tuple.index(max_value)]
      del pri_tuple[0:pri_tuple.index(max_value)]
      pri_tuple.extend(back_lst)
    else:
      pri_tuple.pop(0)
      i+=1
  answer = i
  return answer

• 나의 아이디어:
  현재 리스트에서 max값을 찾고 → 리스트의 첫번째 원소~max값 직전 원소까지 그대로 슬라이싱하여
  → 리스트 맨 끝에 갖다 붙임: max값이 리스트의 맨 앞에 위치하게 됨 → 해당 max를 pop하여 제거 (i +1)
• 매개변수 location이 원본 priorities에 대한 index 값이므로, 원본 index 값을 저장하기 위해 enumerate 사용
  → priorities 리스트의 각 원소가 (idx, value)의 튜플 형태로 저장됨
• while문을 사용 (단, 무한루프의 위험 있으므로 while true는 지양하는 것이 좋음)
• max값을 찾기 위해 튜플로 이루어진 pri_tuple 리스트를 sorted함 (정렬 기준이 value값이므로, key, lambda를 이용)
• 추가 테스트케이스에서 문제가 생겼던 부분 😂
  1) while target_tup in pri_tuple에서, while문 내부의 pri_tuple이 새로 업데이트될 때 마다, 해당 while문의 pri_tuple도 함께 바뀜
  2) 따라서 max_value, max_idx, max_val도 함께 업데이트됨
  3) max_value자체가 튜플 형태이고, pri_tuple 리스트 애 max_value의 대상이 되는 원소 자체는 바뀌지만, 해당 원소 내부의 내용이 바뀌지는 않음 (초반에 enumerate로 정의되었기 때문에) → max_value의 max_idx와 pri_tuple.index(max_value)값은 엄연히 다름!!! 아예 다른 내용을 가리킴.
• pop은 디폴트로 맨 마지막 값을 삭제하지만, 원하는 인덱스의 원소를 삭제할 수도 있음
• 리스트의 조작: del 리스트[삭제할 원소 슬라이싱] / 리스트.extend(연장할 리스트 내용)

https://dojang.io/mod/page/view.php?id=2281 

파이썬 코딩 도장: 22.1 리스트 조작하기

 

모범 풀이

1. any 함수의 활용

def solution(priorities, location):
    queue =  [(i,p) for i,p in enumerate(priorities)]
    answer = 0
    while True:
        cur = queue.pop(0)
        if any(cur[1] < q[1] for q in queue):
            queue.append(cur)
        else:
            answer += 1
            if cur[0] == location:
                return answer

• 원소 하나씩, 하나씩. any니까 괜찮음
• [(i,p) for i,p in enumerate(priorities)]
  list comprehension에서 튜플을 다루는 법! 단순하지만 유용함
• ⭐⭐ 파이썬의 any, all 함수 ⭐⭐
  any() : 하나라도 True인게 있으면 True
  all() : 모두 True여야 True 반환
  →  아큐먼트로 iterable한 객체를 받음. (ex list)
  →  이 객체를 돌면서 조건을 검사해 답을 True/False의 답을 반환
  any(x, y for y in y_list) = True/False
  any()는 특히 대소비교를 할 때 사용하면 sort보다 실행시간을 많이 줄일 수 있다. 예를 들어 어떤 수와 어떤 리스트의 원소들을 비교하는데 해당 수가 리스트 안의 max값보다 큰지만 알고 싶다고 하자. 이 때, sort를 사용한 뒤 비교하면 리스트를 모두 정렬하기 때문에 시간이 걸린다. 하지만 any를 쓰면 리스트 내에 해당 수보다 큰 수가 있기만 하면 바로 True를 return하고 끝내기 때문에 시간이 덜 걸린다. 
  
  if 조건과 함께 다음과 같이 사용할 수도 있다.

cur = 3
temp = [1,3,6,2]
if any(cur<num for num in temp):
	print("There exist number that is larger than 3")

 

2. deque의 활용 -> 효율성 향상

def solution(p, l):
    ans = 0
    m = max(p)
    while True:
        v = p.pop(0)
        if m == v:
            ans += 1
            if l == 0:
                break
            else:
                l -= 1
            m = max(p)
        else:
            p.append(v)
            if l == 0:
                l = len(p)-1
            else:
                l -= 1
    return ans