[코테] 스택/큐

Jessie·2022년 5월 19일
0

코테

목록 보기
1/1

프로그래머스 > 코딩테스트 연습 > 스택/큐

1. 기능개발

문제

각 기능은 진도가 100%일 때 반영할 수 있음.
기능의 개발속도는 모두 다름.
뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있음. 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됨.
배포는 하루에 한 번만, 하루의 끝에 이루어짐.

input

  • progress: 작업의 진도가 적힌 정수 배열
  • speeds: 작업의 개발 속도가 적힌 정수 배열

output

  • 각 배포마다 몇 개의 기능이 배포되는지

풀이

뒤의 작업이 앞의 작업보다 빨리 끝나도 앞의 작업이 빨리 끝날때까지 기다렸다가 같이 배포해야 하는게 핵심인 것 같다. 앞의 작업의 daysLeft(A)가 뒤의 작업의 daysLeft(B)보다 크다면 뒤의 작업의 daysLeft 또한 A인 것이나 마찬가지다.

코드(기본)

from math import ceil

def solution(progresses, speeds):
    daysLeft=[ceil((100-p)/s) for p,s in zip(progresses,speeds)]
    
    answer=[]
    cnt=1
    for i in range(len(daysLeft)-1):
        if daysLeft[i]<daysLeft[i+1]:
                answer.append(cnt)
                cnt=1
        else:
            daysLeft[i+1]=daysLeft[i]
            cnt+=1
    answer.append(cnt)
    return answer

이렇게 해도 맞는데, 예외처리를 사용하는 신박한 방법이 있어서 사용해봤다.

코드(예외처리)

from math import ceil

def solution(progresses, speeds):
    daysLeft=[ceil((100-p)/s) for p,s in zip(progresses,speeds)]
    
    answer=[]
    cnt=1
    for i in range(len(daysLeft)):
        try:
            if daysLeft[i]<daysLeft[i+1]:
                answer.append(cnt)
                cnt=1
            else:
                daysLeft[i+1]=daysLeft[i]
                cnt+=1
        except IndexError:
            answer.append(cnt)
    return answer

2. 프린터

문제

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

input

  • priorities: 현재 대기목록에 있는 문서의 중요도가 순서대로 담긴 배열
  • location: 문서의 위치

output

  • 대기목록에서 location 위치에 있는 문서가 몇 번째로 인쇄되는지

풀이

큐에 인덱스와 우선순위를 튜플로 묶어 저장하고, 우선순위를 내림차순으로 정렬하여 pOrder에 저장한다. pOrder 순으로 프린트되어야 한다.
1. 큐에서 튜플을 pop한다.
2. 튜플의 우선순위가 현재 출력되어야 하는 우선순위인지 확인한다.
2-1. 아니라면 큐에 다시 튜플을 append하고 2로 돌아간다.
2-2. 맞다면 튜플의 index값이 location과 동일한지 확인한다.
2-2-1. 맞다면 반복을 중단한다.
2-2-2. 아니라면 pOrder의 인덱스와 answer를 하나씩 증가시키고 2로 돌아간다.

코드

def solution(priorities, location):
    answer = 1
    queue=[(i,p) for i,p in enumerate(priorities)]  
    pOrder,pIdx=sorted(priorities,reverse=True),0
    while True:
        x=queue.pop(0)
        if x[1]==pOrder[pIdx]:
            if x[0]==location:
                break
            pIdx+=1
            answer+=1
        else:
            queue.append(x)
        
    return answer

3. 다리를 지나는 트럭

문제

트럭이 정해진 순서대로 다리를 건너려 한다.
다리에는 트럭이 bridge_length대 올라갈 수 있다.
다리는 weight 이하까지의 무게를 견딜 수 있다.
모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는가?

input

  • bridge_length: 다리에 올라갈 수 있는 트럭 수
  • weight: 다리가 견딜 수 있는 무게
  • truck_weights: 트럭 별 무게가 담긴 배열

output

  • 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지

풀이

다리의 길이만큼 큐를 잡아놓고, 각 원소를 0으로 초기화하자.
total은 현재 다리에 올라가 있는 트럭의 무게의 합이다.

모든 트럭이 다리에 오를때까지 반복문을 실행하면서 걸리는 시간(answer)을 갱신한다.
1. 다리의 가장 앞에 있는 트럭(혹은 0)을 빼내고, total을 갱신한다.
2. 대기중인 트럭이 다리에 올랐을 때
2-1. weight을 초과하지 않으면 다리에 트럭을 올리고 total을 갱신한다.
2-2. 초과한다면 0을 올린다.

모든 트럭이 대기상태를 벗어나 다리를 건넜거나 다리에 올라가 있는 상태가 되었을 때, 큐의 길이는 마지막 트럭이 다리를 건너기 위해 필요한 시간이 되니 answer에 큐의 길이를 더해준다.

코드

def solution(bridge_length, weight, truck_weights):
    queue=[0 for _ in range(bridge_length)]
    answer,total=0,0

    while(len(truck_weights)!=0):
        
        answer+=1
        truckPopped=queue.pop(0)
        total-=truckPopped
        if(total+truck_weights[0]<=weight):
            truckPushed=truck_weights.pop(0)
            queue.append(truckPushed)
            total+=truckPushed
        else:
            queue.append(0)

    answer+=len(queue)
    return answer

4. 주식 가격

문제

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return

풀이

간단하게 이중 for문을 사용해도 통과하는 문제였다.
시간복잡도가 O(N²)인데 더 효율적인 방법은 없을까?

코드

def solution(prices):
    answer = []
    for i in range(len(prices)):
        for j in range(i+1,len(prices)):
            if prices[i]>prices[j]:
                break
        answer.append(j-i)
    return answer

0개의 댓글