1. 기능개발
문제 설명
프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.
또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.
먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.
제한 사항
- 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
- 작업 진도는 100 미만의 자연수입니다.
- 작업 속도는 100 이하의 자연수입니다.
- 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.
입출력 예
| progresses | speeds | return |
|---|---|---|
| [93, 30, 55] | [1, 30, 5] | [2, 1] |
| [95, 90, 99, 99, 80, 99] | [1, 1, 1, 1, 1, 1] | [1, 3, 2] |
입출력 예 설명
입출력 예 #1
첫 번째 기능은 93% 완료되어 있고 하루에 1%씩 작업이 가능하므로 7일간 작업 후 배포가 가능합니다.
두 번째 기능은 30%가 완료되어 있고 하루에 30%씩 작업이 가능하므로 3일간 작업 후 배포가 가능합니다. 하지만 이전 첫 번째 기능이 아직 완성된 상태가 아니기 때문에 첫 번째 기능이 배포되는 7일째 배포됩니다.
세 번째 기능은 55%가 완료되어 있고 하루에 5%씩 작업이 가능하므로 9일간 작업 후 배포가 가능합니다.
따라서 7일째에 2개의 기능, 9일째에 1개의 기능이 배포됩니다.
입출력 예 #2
모든 기능이 하루에 1%씩 작업이 가능하므로, 작업이 끝나기까지 남은 일수는 각각 5일, 10일, 1일, 1일, 20일, 1일입니다. 어떤 기능이 먼저 완성되었더라도 앞에 있는 모든 기능이 완성되지 않으면 배포가 불가능합니다.
따라서 5일째에 1개의 기능, 10일째에 3개의 기능, 20일째에 2개의 기능이 배포됩니다.
배열로 풀기
def solution(progresses, speeds):
remain_list = []
for i in range(len(progresses)):
remain = 100 - progresses[i]
time = remain // speeds[i] + (1 if remain % speeds[i] != 0 else 0)
remain_list.append(time)
remain_list.append(101)
curr = remain_list[0]; total = 0
answer = []
for remain in remain_list:
if curr < remain:
curr = remain
answer.append(total)
total = 1
else:
total += 1
return answer작업이 끝나기까지 남은 일수를 remain_list 에 담아두고
현재까지 기능을 배포할 때 걸리는 일수를 curr에 저장하고
다음 일수가 더 크다면 curr 을 갱신하고 answer에 추가
다음 일수가 작거나 같다면 total 으로 기능 개수를 축적시킨다.
다만 이 경우는 마지막 경우가 answer 에 추가하지 못하기 때문에 제한사항보다 큰 숫자를 넣어서 무조건 추가하도록 한다.
최적화
import math
def solution(progresses, speeds):
answer = []
curr = math.ceil((100 - progresses[0]) / speeds[0])
total = 1
for i in range(1, len(progresses)):
remain = math.ceil((100 - progresses[i]) / speeds[i])
if remain > curr:
answer.append(total)
curr = remain
total = 1
else:
total += 1
answer.append(total) # 마지막 묶음 처리
return answer굳이 remain_list에 담지 않고도 매번 curr과 비교하는 변수를 그때마다 progesses와 speeds에서 계산해서 가져온다.
생각해야 할 것
answer 배열에 갱신하는 과정에서 변수를 어떻게 초기값을 잡을지 복잡하기 때문에
주석으로 시뮬레이션 하면서 차근차근 정리해야 한다.
2. 올바른 괄호
문제 설명
괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어
- "()()" 또는 "(())()" 는 올바른 괄호입니다.
- ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.
'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.
제한사항
- 문자열 s의 길이 : 100,000 이하의 자연수
- 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.
입출력 예
| s | answer |
|---|---|
| "()()" | true |
| "(())()" | true |
| ")()(" | false |
| "(()(" | false |
Deque를 활용해서 풀기
from collections import deque
def solution(s):
d = deque()
for i in s:
if i == "(":
d.append(1)
else:
try:
d.pop()
except:
return False
if d:
return False
return True열린괄호라면 deque에 원소를 하나 삽입하고, 닫힌괄호라면 deque에서 원소를 하나 뺀다.
이 과정동안에 원소가 없는데 원소를 뺀다면 False, 과정이 끝나고 원소가 남아있다면 False다.
나머지는 True다.
deque에서 pop은 비어있다면 IndexError를 보내기 때문에 try-except 문을 통해서 처리한다.
3. 프로세스
문제 설명
운영체제의 역할 중 하나는 컴퓨터 시스템의 자원을 효율적으로 관리하는 것입니다. 이 문제에서는 운영체제가 다음 규칙에 따라 프로세스를 관리할 경우 특정 프로세스가 몇 번째로 실행되는지 알아내면 됩니다.
규칙
- 실행 대기 큐(Queue)에서 대기중인 프로세스 하나를 꺼냅니다.
- 큐에 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있다면 방금 꺼낸 프로세스를 다시 큐에 넣습니다.
- 만약 그런 프로세스가 없다면 방금 꺼낸 프로세스를 실행합니다.
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 … 과 같이 표현합니다.
입출력 예
| priorities | location | return |
|---|---|---|
| [2, 1, 3, 2] | 2 | 1 |
| [1, 1, 9, 1, 1, 1] | 0 | 5 |
입출력 예 설명
예제 #1
문제에 나온 예와 같습니다.
예제 #2
6개의 프로세스 [A, B, C, D, E, F]가 대기 큐에 있고 중요도가 [1, 1, 9, 1, 1, 1] 이므로 [C, D, E, F, A, B] 순으로 실행됩니다. 따라서 A는 5번째로 실행됩니다.
Queue로 풀기
import queue
def solution(priorities, location):
que = queue.Queue()
for i in range(len(priorities)):
que.put((priorities[i], i))
priority = sorted(priorities, reverse=True)
index = 0
answer = []
while not que.empty():
prior, num = que.get()
if prior == priority[index]:
index += 1
answer.append(num)
else:
que.put((prior, num))
return answer.index(location) + 1파이썬에서 Queue는 put(), get(), empty(), qsize()만 기억해도 충분한 것 같다.
우선순위가 주어지기에 우선순위 큐를 사용해야 할 것 같지만, 우선순위 큐의 작동방식만으로는 규칙대로 작동하게 만들기 곤란하다.
규칙에서는 마치 원형 큐 처럼 순서대로 조사하는 방식이지만 우선순위 큐라면 같은 우선순위의 경우 그 다음 요소의 정렬 방식에 따라 순서가 달라지기 때문이다.
큐에 각 우선순위와 location 값에 해당하는 index값을 넣어주고,
우선순위가 높은 순부터 차례대로 비교하면서 가장 높은 우선순위의 프로세스부터 빼내도록 반복문을 돌려주면 된다.
그럼 가장 높은 우선순위의 프로세스부터 index값이 answer 배열에 들어가기 때문에 answer.index(location) 을 통해 정답을 찾아낼 수 있다.
4. 다리를 지나는 트럭
문제 설명
트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 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 이하입니다.
입출력 예
| bridge_length | weight | truck_weights | return |
|---|---|---|---|
| 2 | 10 | [7,4,5,6] | 8 |
| 100 | 100 | [10] | 101 |
| 100 | 100 | [10,10,10,10,10,10,10,10,10,10] | 110 |
문제 풀이
import queue
def solution(bridge_length, weight, truck_weights):
# 초기 세팅
que = queue.Queue(maxsize=bridge_length)
for i in range(bridge_length):
que.put(0)
curr_weights = 0
curr_time = 0
for truck in truck_weights:
# 들어갈 수 없는 상태라면 맨 앞 트럭 나갈 때까지 기다리고 넣기
if curr_weights + truck > weight:
# 넣을 수 있을 때까지 트럭 빼기
while True:
index = 0
# 트럭 빼기위해 이동시키기
while True:
index = que.get()
curr_weights -= index
# 트럭 나가기 직전 다음 단계에서 시간 늘리도록 조정
if index != 0:
break
que.put(0)
curr_time += 1
if curr_weights + truck <= weight:
break
que.put(0)
curr_time += 1
curr_weights += truck
que.put(truck)
curr_time += 1
# 들어갈 수 있는 상태라면 바로 넣기
else:
curr_weights += truck
curr_weights -= que.get()
que.put(truck)
curr_time += 1
# 맨 마지막에 트럭을 들여보냈으므로 남은 시간을 더해주기만 하면 됨
curr_time += bridge_length
return curr_time큐를 이용해서 풀었는데, 다리 길이의 모든 칸을 0으로 채워넣고 get()과 put()을 반복하는 방식으로 진행하도록 했다.
- 트럭을 다 집어넣는다.
- 마지막 트럭을 집어넣었으면 그 트럭만 나가면 되니
다리 길이만큼 시간에 더해주면 된다.
크게 보면 이러한 과정으로 진행하고, 1번을 구체화하면
- 트럭이 들어갈 수 있는가?
- 못 들어간다.
- 트럭이 들어갈 때 까지 트럭을 뺀다.
- 들어갈 수 있게 되면 그 때 넣는다.
- 들어간다.
- 트럭을 넣는다.
- 못 들어간다.
트럭이 들어갈 때까지 빼기 위해 2중 while문을 썼다.
첫 번째 while문은 트럭을 뺐을 때 아직 정원초과가 우려될 때 반복시키기 위해
두 번째 while문은 트럭을 빼기 위해 트럭이 올 때까지 이동(0을 get하고 put 반복)하기 위해
이 과정에서 curr_weight와 curr_time을 잘 관리하는 것이 매우 중요했다.
