스택과 큐

<프로그래머스 고득점kit>

<기능개발>

def solution(progresses, speeds):
    answer = []
    while(len(progresses)>0):
      days=1
      while(speeds[0]*days+progresses[0]<100):
        days+=1
      count=1
      progresses.pop(0) 
      speeds.pop(0)
      while(len(progresses)>0 and (progresses[0]+days*speeds[0]>=100)):
        count+=1
        progresses.pop(0)   
        speeds.pop(0)
      answer.append(count) 
    return answer

<해설>

앞에서 부터 끝나면 앞을 먼저 추출하기에 큐개념을 쓴다.
가장 앞에 있는 작업이 끝나는 일을 계산하고 완료되면 추출후 저장된 일수를 이용해 다음 작업을 탐색하며 같은 일수가 지났을 때 완료된 상태면 계속 추출해 나가는 방식으로 구현한다.

<프린터>

from collections import deque
def solution(priorities, location):
  indexlist=[i for i in range(len(priorities))]
  dqindex=deque(indexlist)
  dqpri=deque(priorities)
  answer=[]
  l=len(priorities)
  for i in range(l):
    listpri=list(dqpri)
    maxindex=listpri.index(max(listpri))
    for i in range(maxindex):
      sub=dqindex.popleft()
      dqindex.append(sub)
      sub=dqpri.popleft()
      dqpri.append(sub)
    answer.append(dqindex.popleft())
    dqpri.popleft()
    index=list(dqindex)
  for i,v in enumerate(answer):
    if(v==location):
      return i+1;

<해설>

인덱스 지도를 함께 만들어 priorities를 순회하며 큰수를 찾고 큰 수의 왼쪽은 모두 추출하면서 오른쪽에 쌓으면서 인덱스 지도도 같이 최신화한다.이때 이미 알아낸 큰수는 삭제시키고 나머지 리스트에서 같은 로직을 반복한다.

<전화번호 목록>

def solution(phone_book):
  hash={}
  for phone_number in phone_book:
    hash[phone_number]=1
  for phone_number in phone_book:
    word=''
    for ch in phone_number:
      word+=ch
      if(word!=phone_number and word in hash):
        return False
  return True
#
num=int(input())
ob(num)

<해설>

현재의 단어를 보았을때 앞에서부터 단어의 알파벳을 완성시키면서 해쉬에 존재하는지를 탐색하고 해쉬에 존재한다면 현재 보고 있는 단어의 접두사이다.

<위장>

from itertools import combinations
def solution(clothes):
    hash={}
    for [cloth,cate] in clothes:
      if(hash.get(cate,False)==False):
        hash[cate]=1
      else:
        hash[cate]=hash[cate]+1
    cate_len=len(hash)
    if(cate_len==30):
      return 1073741823
    cate_list=hash.values()
    comb=[]
    for i in range(1,cate_len+1):
      comb+=list(combinations(cate_list,i))
    count=0
    for i in comb:
      sub=1
      for v in i:
        sub*=v
      count+=sub
    return count

<해설>

종류에 대한 종류의 수로 이루어진 리스트를 만들고 종류의 수까지 조합을 만들며 각 리스트의 곱의 합을 하면 된다.

예외사항:종류가 30개면 조합을 구하는 연산이 느려져 시간초과가 되기 때문에 미리 계산된 값으로 바로 반환하여 끝낸다.