알고리즘 문제와의 만남
이전에 알고리즘 문제를 몇 번 풀어보았다. 나름 괜찮았던 것 같다. 하지만, 우물 안 개구리였을 뿐이다. 자료구조를 배우면서 알게 된 알고리즘 문제는 저세상인 것 같다.
눈으로는 스택과 큐가 무엇인지 '알지 알지'하고 있었지만, 막상 머리는 '?'(물음표)로 반응하고 있었다.
너무 쉽게 생각했던 나에게 한 방 먹여준 문제였다.
누구나 그럴싸한 계획은 있다. 쳐맞기 전까진...
어제부터 문제에 두들겨 맞다 보니 스트레스가 쌓인다. 하지만, 성격상 포기할 수가 없다. 다 풀어야 직성이 풀릴 것 같았기에 일단 그냥 매달려본다.
문제를 이해할 수 없어서 한 시간.
그리고 다른 사람들의 풀이를 이해하려고 한 시간.
또다시 스택과 큐를 들여다보고 문제를 이해하는데 한 시간.
그리고 문제를 해결하는데 두 시간.
결국, 의사 코드를 작성하고 오류를 하나씩 잡아나가면서 문제를 해결할 수 있었다.
문제를 풀이하자면, solution 함수에 들어가는 숫자 리스트는 각 시간(초)에 해당하는 주식의 가격이다.
예를 들자면
1초 1원
2초 2원
3초 3원
4초 2원
5초 3원
여기서 각 가격에 대해 얼마나 유지되거나 상승하는지를 return하는 문제이다.
1초 : solution[0] = 1
4초라는 시간(리스트의 길이) 동안 1원이라는 가격보다 내려가는 경우는 없었기에 4초간 가격이 유지된다.
2초 : solution[1] = 2
3초라는 시간 동안에도 2원이라는 가격보다 내려가는 경우는 없으니 3초간 가격이 유지된다.
3초 : solution[2] = 3
3원의 가격에서 다음 가격은 2원이다. 결국, 1초 후에 가격이 내려간다. 여기서 가격이 유지되는 시간은 1초이다.
4초 : solution[3] = 2
2원의 가격은 남은 1초 동안 떨어지지 않았으므로 1이 반환된다.
5초 : solution[4] = 3
마지막으로 3원이 되면서 장이 마감?된다. 여기서 3원이 되면서 마감됐으므로 0이 반환된다.
처음 아무 힌트도 없이 문제를 보았을 때는 규칙을 찾으려 노력했지만, 그런 건 없었다. 문제의 설명이 부족했던 것 같다.
문제를 이해한 후 코랩을 이용해 풀어보았다.
def solution(prices):
w = True
k = 0 # 1씩 올라가는 값
result = []
while w==True:
for i in range(k,len(prices)): # k부터 끝까지
if prices[k] > prices[i]: # k보다 i가 작을 때 (가격이 내려갔을 때)
result.append(i-k) # k(price[k]의 위치) - i(prices[i]의 위치)를 result에 포함
break
elif (i == len(prices)-1) and prices[i] >= prices[k]: #마지막에 비교한 i값이 k와 같거나 i가 더 클 때
result.append(len(prices) - k-1) #전체 시간(리스트의 크기)에서 k -1 을 뺀 시간을 result에 포함
break
k += 1
if k == len(prices): #k가 prices 길이가 같으면 False 출력하여 while문 탈출
w = False
return result결과는?
통과!
느낀 점 : 쓰고 수정하면서 한 시간 반 정도가 걸린 것 같다. 결국은 풀어내면서 뿌듯함을 느꼈다. 문제를 시작하기 전부터 느꼈지만, append를 썼다는 것에서는 스택, 큐 문제일 수 있지만, 결론적으로는 탐색문제가 아니었나 싶다.
그리고 이번 문제를 통해 더욱 알고리즘 공부가 필요하다는 것을 느꼈다.
