스택/큐

1. 기능개발 lv.2

프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.

또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.

먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.

제한 사항

• 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
• 작업 진도는 100 미만의 자연수입니다.
• 작업 속도는 100 이하의 자연수입니다.
• 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.

from collections import deque
def solution(progresses, speeds):
    # progresses[0]이 배포될 때, 몇 개의 progress가 배포될 것인가
    # 우선되는 progress가 완료되어야 연속적으로 배포 가능 -> deque
    progresses=deque(progresses)
    speeds=deque(speeds)
    answer = []
    
    while progresses:
        cnt=0   # 연속적으로 배포될 progress

        while progresses and progresses[0]>=100:    # 전부 pop 된 후에는 index 접근불가하기에 리스트 체크 우선해야함
            cnt+=1
            progresses.popleft()
            speeds.popleft()
        
        for i,s in enumerate(speeds):
            progresses[i] += s
        
        if cnt:
            answer.append(cnt)
        
    return answer

 

 

 

2. 올바른 괄호 lv.2

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어

• "()()" 또는 "(())()" 는 올바른 괄호입니다.
• ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.

'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

제한사항

• 문자열 s의 길이 : 100,000 이하의 자연수
• 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

def solution(s):
    # 문자열에서 ()를 지워나가기
    # ( 발견하면 어팬드, ) 발견하면 팝
    
    stack=[]
    if s[0]==')':
        return False
    
    for c in s:
        if c=='(':
            stack.append(c)
        else:   # ')'일 때
            if stack:   #'('짝이 있으면
                stack.pop()
            else:
                return False
        
    if stack:
        return False
    else:
        return True

 

 

 

3. 프로세스 lv.2

운영체제의 역할 중 하나는 컴퓨터 시스템의 자원을 효율적으로 관리하는 것입니다. 이 문제에서는 운영체제가 다음 규칙에 따라 프로세스를 관리할 경우 특정 프로세스가 몇 번째로 실행되는지 알아내면 됩니다.

1. 실행 대기 큐(Queue)에서 대기중인 프로세스 하나를 꺼냅니다.
2. 큐에 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있다면 방금 꺼낸 프로세스를 다시 큐에 넣습니다.
3. 만약 그런 프로세스가 없다면 방금 꺼낸 프로세스를 실행합니다.
  3.1 한 번 실행한 프로세스는 다시 큐에 넣지 않고 그대로 종료됩니다.

예를 들어 프로세스 4개 [A, B, C, D]가 순서대로 실행 대기 큐에 들어있고, 우선순위가 [2, 1, 3, 2]라면 [C, D, A, B] 순으로 실행하게 됩니다.

현재 실행 대기 큐(Queue)에 있는 프로세스의 중요도가 순서대로 담긴 배열 priorities와, 몇 번째로 실행되는지 알고싶은 프로세스의 위치를 알려주는 location이 매개변수로 주어질 때, 해당 프로세스가 몇 번째로 실행되는지 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• priorities의 길이는 1 이상 100 이하입니다.
  • priorities의 원소는 1 이상 9 이하의 정수입니다.
  • priorities의 원소는 우선순위를 나타내며 숫자가 클 수록 우선순위가 높습니다.
• location은 0 이상 (대기 큐에 있는 프로세스 수 - 1) 이하의 값을 가집니다.
  • priorities의 가장 앞에 있으면 0, 두 번째에 있으면 1 … 과 같이 표현합니다.

from collections import deque

def solution(priorities, location):
    queue = [(i, p) for i,p in enumerate(priorities)]
    queue = deque(queue)
    
    answer = 0
    
    while queue:
        cur = queue.popleft() # popleft, (i,p) 형태
        
        if any(cur[1] < q[1] for q in queue):   # 큐 내 우선순위 최댓값보다 cur의 우선순위가 작은 경우
            queue.append(cur)
        else:
            answer += 1
            if cur[0] == location:
                return answer

 

 

 

4. 다리를 지나는 트럭 lv.2

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.

예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

경과 시간	다리를 지난 트럭	다리를 건너는 트럭	대기 트럭
0	[]	[]	[7,4,5,6]
1~2	[]	[7]	[4,5,6]
3	[7]	[4]	[5,6]
4	[7]	[4,5]	[6]
5	[7,4]	[5]	[6]
6~7	[7,4,5]	[6]	[]
8	[7,4,5,6]	[]	[]

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

제한 조건

• bridge_length는 1 이상 10,000 이하입니다.
• weight는 1 이상 10,000 이하입니다.
• truck_weights의 길이는 1 이상 10,000 이하입니다.
• 모든 트럭의 무게는 1 이상 weight 이하입니다.

from collections import deque

def solution(bridge_length, weight, truck_weights):
    # 한 트럭당 다리를 지나는 데 걸리는 시간 -> brigdge_length
    # 대기 순서대로 지나감
    answer = 0
    queue = deque(truck_weights)
    curB = deque([0] * bridge_length)   # 현재 다리 위 상황 bridge_length
    curW = 0 # 현재 다리 무게
    
    while curB:
        answer += 1
        
        # 트럭 내보내기
        if curB[0] != 0:
            curW -= curB[0]
        curB.popleft()
        
        # 트럭 추가: 무게 체크
        if queue:
            if weight - curW >= queue[0]:   # 트럭 더 올릴 수 있음
                curW += queue[0]
                curB.append(queue.popleft())
            else:
                curB.append(0)  # 트럭 이동

    return answer

 

 

 

5. 주식 가격 lv.2

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.제한사항

• prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
• prices의 길이는 2 이상 100,000 이하입니다.

입출력 예

prices: [1, 2, 3, 2, 3]

return: [4, 3, 1, 1, 0]

• 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
• 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
• 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
• 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
• 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

from collections import deque

def solution(prices):
    answer = []
    prices = deque(prices)
    
    while prices:
        cur = prices.popleft()
        count = 0
        
        for price in prices:
            count += 1  # 1초 뒤에 가격이 떨어져도 1초간은 유지한 것으로 봄
            
            if cur > price:   # 하락
                break
                
        answer.append(count)

    return answer