[프로그래머스] 주식가격 (python)
문제설명
Idea
- prices를 차례대로 방문
- 방문한 price와 그 뒤 prices를 비교하며 탐색
- 가격을 고려하여 시간 1초씩 증가 (몇초부터 주식가격이 떨어지는 알아내기 위한 목적)
- 모든 prices를 돌때까지 반복
고려 조건
- price보다 큰 값이 있다면 가격이 떨어지지 않았기 때문에 1초 증가
- price보다 작은 값이 있다면 가격이 떨어졌다는 의미이므로 이 때까지 증가했던 '초' 계산
Solution
def solution(prices):
# 0.02500254016666667
N = len(prices)
answer = [-1] * N
for i in range(N):
for j in range(i+1, N):
if prices[i] > prices[j]:
answer[i] = j-i
break
if answer[i] == -1:
answer[i] = N-i-1
return answer
초기 answer는 prices 길이만큼 -1로 초기화합니다.
이후 prices[0]와 prices[1..4], prices[1]과 prices[2..4] 형식으로 비교를 진행합니다. ( []의 숫자는 배열 인덱스 )
비교 시 고려해야하는 조건은 총 2가지 입니다.
1.
prices[i] 값 보다 prices[i+1..N]에 값들이 전부 크다면( prices[i] > prices[j] 만족 X ) i 위치에서 N까지 주식가격 하락이 없음을 의미합니다.
위 조건은 i 위치부터 N까지 가격이 떨어지지 않았다는 의미이므로, 이 조건을 만족할 수 있게 answer[i]에 N-i-1을 넣어줍니다.
※ i(인덱스)부터 배열의 끝(N)까지의 차를 구해야해서 N-i를 하고, 배열의 시작은 0부터이니 주식가격이 떨어지는 시간을 구하기 위한 조건을 충족하기 위해 -1을 해주었습니다.
2.
prices[i] 값 보다 prices[i+1..N]에 값 중 작은 값이 있다면 ( prices[i] > prices[j] 만족 ) N초 뒤 주식가격이 떨어졌음을 의미합니다.
주식가격이 떨어졌다는 의미는 i부터 j-1까진 주식가격 하락이 없다가 j부터 주식가격이 떨어진다는 의미입니다.
이 조건을 만족할 수 있게 answer[i]에 j-i를 넣어줍니다.
※ i에서 주식가격이 떨어지는 시점인 j 사이에 차를 구해야하기 때문에 j-i를 해주었습니다.
위 2가지 경우를 고려한 방법으로 주식가격 문제를 풀었습니다.
import timeit
avg_time = 0.
tests = [[1, 2, 3, 2, 3],
[5, 4, 3, 2, 1],
[5, 1],
[5, 4, 10, 5],
[5, 5, 5, 5],
[1, 5, 6, 5, 2, 4, 77, 0]]
for t in tests:
avg_time += timeit.timeit(lambda: solution(t), number=10000)
print(f'avg_time: {avg_time / len(tests)}')
제가 푼 방식은 대략 0.025초 정도 걸리는 것으로 파악되었습니다.
Refactoring
def solution(prices):
# 0.016480596
N = len(prices)
ans = [0] * N
stack = [0]
for i in range(1, N-1):
if prices[i] < prices[stack[-1]]:
for j in stack[::-1]:
if prices[i] < prices[j]:
ans[j] = i-j
stack.remove(j)
else:
break
stack.append(i)
for s in stack:
ans[s] = N-s-1
return ans
리펙토링에서는 0번째 인덱스를 stack에 넣은 상태에서 시작합니다.
i는 1부터 stack[-1]에 있는 인덱스를 prices에 넣어 값들( prices[i] < prices[stack[-1]] )을 비교합니다.
주식값이 떨어지는지 알아내기 위해서는 '이전' 주식값과 '현재' 주식값을 비교해야합니다.
stack에는 '이전' 주식값 인덱스를 넣어 '현재' 주식값과 비교하기 위한 용도로 사용합니다.
포문에서 N-1만큼 도는 이유는 문제(주식가격)에 주어진 경우를 살피면 prices[-1]은 주식가격이 0초간 하락하게 됩니다. 이를 고려하여 ans[-1]을 0으로 초기화하면 prices[-1]에 대한 계산이 필요없어 N-1만큼만 포문을 돕니다.
1.
모든 케이스가 prices[i] < prices[stack[-1]]을 만족하지 않는 경우로 설명합니다.
prices: [1, 2, 3, 4, 5]
stack에 해당 i(인덱스)를 추가합니다. ( if prices[i] < prices[stack[-1]] 만족 X )
이후 포문을 빠져나온 뒤 새로운 포문을 돕니다.
stack remove 되지않은 stack 값(인덱스)들은 해당 값 부터 N까지 주식값이 떨어지지 않았음을 의미합니다.
이 조건을 만족할 수 있게 ans[s]에 N-s-1을 넣어줍니다.
※ s(인덱스 값을 가지고 있음)부터 배열의 끝(N)까지의 차를 구해야해서 N-s를 하고, 배열의 시작은 0부터이니 주식가격이 떨어지는 시간을 구하기 위한 조건을 충족하기 위해 -1을 해주었습니다.
2.
모든 케이스가 prices[i] < prices[stack[-1]]을 만족하는 경우로 설명합니다.
모든 케이스가 prices[i] < prices[stack[-1]]을 만족하는 경우로 설명합니다.
prices: [5, 4, 3, 2, 1]
stack은 0으로 초기화되어있으니 stack[-1]은 최초에 0을 반환합니다.
prices[i] < prices[stack[-1]]을 만족할 경우 stack을 역순하여 값들을 가져옵니다. (stack 특성 - LIFO)
이후 prices[i] < prices[j](stack에 있는 '이전' 주식값)를 비교합니다.
위 조건(prices[i] < prices[j])을 충족한다는 의미는 j 위치에는 주식가격 하락이 없다가 i 위치부터 주식가격이 떨어졌다는 의미이며, 이를 만족하기 위해 ans[j]에 i-j를 넣어주고 해당 stack은 remove합니다.
※ i는 '현재' 주식값의 위치이고 j는 '이전' 주식값의 위치입니다. j부터 주식가격이 떨어지는 시점인 i 위치 사이에 차를 구해야하기 때문에 i-j를 해주었습니다.
위 2가지 경우를 고려한 방법으로 주식가격 문제를 리펙토링 하였습니다.
import timeit대략 0.016초 정도 걸리는 것으로 파악되었습니다.
avg_time = 0.
tests = [[1, 2, 3, 2, 3],
[5, 4, 3, 2, 1],
[5, 1],
[5, 4, 10, 5],
[5, 5, 5, 5],
[1, 5, 6, 5, 2, 4, 77, 0]]
for t in tests:
avg_time += timeit.timeit(lambda: solution(t), number=10000)
print(f'avg_time: {avg_time / len(tests)}')
리펙토링을 통해 기존 0.025초에서 0.016초로 대략 56% 정도 성능이 개선되었습니다.
전체 코드는 아래 깃허브에서 확인 가능합니다.
댓글
댓글 쓰기