[프로그래머스] lv2 #42584 주식가격 / #42586 기능개발 / #42583 다리를 지나는 트럭
스택과 큐 개념을 연습하기 위하여 3개의 연습문제(주식가격, 기능개발, 다리를 지나는 트럭문제)를 풀었다.
1. #42584 주식가격
문제
초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어진다. 이 때, 주식의 가격이 떨어지지 않은 기간이 몇 초인지를 return 하도록 solution 함수를 완성하라.
제한사항
- prices의 각 가격은 1 이상 10,000 이하인 자연수
- prices의 길이는 2 이상 100,000 이하
입출력 예
| prices | return |
|---|---|
| [1, 2, 3, 2, 3] | [4, 3, 1, 1, 0] |
- 3초 시점의 ₩3은 1초뒤에 가격이 떨어진다. 따라서 1초간 가격이 떨어지지 않은 것으로 본다.
- 5초 시점의 ₩3은 0초간 가격이 떨어지지 않는다고 본다. (return의 마지막 값은 무조건 0)
풀이
def Solution(prices):
def solution(prices):
answer = []
for i in range(len(prices)):
st_pr = prices[i]
cnt = 0
j = i
while j < (len(prices) - 1): # 마지막 값은 비교가 무의미하므로 이렇게 조건을 달아줌
if st_pr > prices[j]:
break
else:
j += 1
cnt += 1
answer.append(cnt)
return answer
해설
핵심은 prices의 값들 각각을 기준값으로 잡고, prices 내에서 기준값보다 작은 값이 나타날 때 까지 리스트를 검사하며 검사한 값의 갯수를 저장하여, 이를 answer에 반영한다.
- st_pr은 기준값이다. prices에서 for문을 돌려 각 값을 순서대로 하나씩 기준값으로 잡아준다.
- j는 기준값 이후의 값들을 검사하기 위한 for문 인자이다.
- cnt는 기준값 미만의 값이 나올때 까지 코드를 반복한 횟수를 저장하며, 이것이 곧 answer의 값으로 추가된다.
- answer의 마지막 값은 무조건 0이므로, 코드 중간의 while문에 들어가지 않도록 조건을 걸었다.
스택을 활용해보고자 했으나 코드 실행 시간을 감안하면 for문과 while문을 통해 효율적으로 짜는게 더 좋다고 판단하여 이렇게 문제를 풀었다.
2. #42586 기능개발
문제
먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 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일간 작업 후 배포가 가능하다.
풀이
def solution(progresses, speeds):
answer = []
days = []
a = len(progresses)
# 각 기능별로 업데이트에 걸리는 일 수 계산하여 배열로 반환(days)
for i in range(a):
quotient = (100 - progresses[i]) // speeds[i]
remainder = (100 - progresses[i]) % speeds[i]
if remainder == 0:
day = int(quotient)
else:
day = int(quotient) + 1
days.append(day)
x = 0
while True:
if x == len(days):
break
else:
y = x + 1
cnt = 1
while True:
if y == len(days):
x += cnt
break
else:
if days[x] < days[y]:
answer.append(cnt)
x += cnt
break
else:
y += 1
cnt += 1
answer.append(cnt)
return answer
해설
-
크게 2단계로 구성되는 코드로, 먼저 각 작업을 마치는데 걸리는 기간을 저장하는 days 리스트를 만든다.
-
이 days 리스트에서 값들을 비교하여 답을 구해내었다.
-
아쉬운 점은, 내가 이 문제를 풀었을 때에 while문 조건을 많이 써보지 않아서 비효율적인 코드가 짜여진 느낌이 들었다.
- 예를 들어, if y == len(days): 같은 if문을 두어 while문을 빠져나가도록 했는데 사실, 그 위에서 while y< len(days): 을 썼으면 자연스럽게 루프를 빠져나갈 수 있었을 것이다.
추가로, 답안을 제출하고 나서 다른 사람들의 풀이를 보았는데 상당히 인상 깊은 것들이 많았다.
아무래도 개인적으로 내 풀이에 아쉬움이 많었던지라 개선의 여지를 찾고자 더 열심히 풀이들을 읽어보았다.
아래에 그 중에 가장 인상깊었던 풀이를 첨부한다.
인상적인 풀이
def solution(progresses, speeds):
Q=[]
for p, s in zip(progresses, speeds):
if len(Q)==0 or Q[-1][0]<-((p-100)//s):
Q.append([-((p-100)//s),1])
else:
Q[-1][1]+=1
return [q[1] for q in Q]
3. #42583 다리를 지나는 트럭 문제
문제
트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 한다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 하는데, 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시한다.
예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있다고 하자. 무게가 [7, 4, 5, 6]kg인 4대의 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 할 것이다.
| 경과 시간 | 다리를 지난 트럭 | 다리를 건너는 트럭 | 대기 트럭 |
|---|---|---|---|
| 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] | [] | [] |
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 |
나의 답안
def solution(bridge_length, weight, truck_weights):
answer = 0
q = [0] * bridge_length
while q:
answer += 1
q.pop(0)
if truck_weights:
if sum(q) + truck_weights[0] <= weight:
q.append(truck_weights.pop(0))
else:
q.append(0)
else:
answer += (bridge_length - 1)
break
return answer
해설
- q는 다리를 의미하며 초기에 주어진 다리길이 만큼의 갯수로 0이 채워져 있는 Queue 개념이다.
-
트럭이 진입할 때 마다 q 맨 앞의 값이 get(=pop(0))되어 떨어져나가고, truck_weight에서 첫번쨰 트럭을 get하여 q 마지막 부분에 push한다.
-
만약, 현재 트럭 추가시 무게제한에 걸린다면, 새로운 트럭을 추가하는 것이 아니라 그대로 0을 추가한다.
-
이 작업을 매 시간단위마다 반복하도록 while문으로 묶어준다.
- 마지막 트럭이 진입한 경우, 그 트럭이 빠져나가는 시간만 마지막에 더해주면 되므로 else문에 넣어 적용 후에 곧바로 루프를 탈출시킨다. (if truck_weights: 에서 truck_weights = []이므로 else문이 적용된다.)
- 사실 이 부분이 없어도 코드가 돌아가지만, 마지막에 굳이 q에서 0을 하나씩 get하는 것 보다 효율적이므로 이렇게 코드를 구성했다.
Leave a comment