잡담.
-
오늘이 개천절인지 모르고 있었다..
-
리트코드는 백준에 비해 배려가 넘치는 사이트 같다는 생각이 든다.(물론 최상위 난이도 문제는 없는 것 같지만..) 풀이를 제출했을 때 틀린, 혹은 시간초과가 난 케이스에 대해 그 예시를 그대로 보여주는 덕분에 이 코드를 검토할 때 이왜틀?이 거의 없는 편이다.
- 결론 : 아주 좋쿤!
문제 설명.
string colors와 color와 길이가 같은 list neededTime이 주어진다.
colors에 적힌 것은 소문자들의 나열로 한 줄로 이어져있는 연속된 풍선들의 색깔을 나타낸다. neededTime의 원소에는 각 위치의 풍선을 때는데 드는 비용이다.
문제의 목표는 최소의 시간 비용을 들이면서, 한줄로 이어져있는 연속된 풍선들의 색깔이 서로 연속되지 않게 만드는 것이다.
예시를 들어보자.
colors가 abcaab라고 할 때 목표는 이 풍선들의 색깔이 abcab가 되게 만드는 것이고, 결과적으로 4번째 혹은 5번째 풍선을 제거하면 된다.
만약 neededTime == [1,3,5,7,6,4] 라고 가정하면 abcab를 만들기 위해 7 혹은 6의 비용이 들기 때문에 6을 출력해주면 된다.
풀이방법.
별다른 좋은 아이디어가 떠오르지 않아 초기 결과 result를 0으로 두고, 배열을 돌며 같은 색이 2개 이상 붙어있을 때 연속된 비용의 합에 최대 값을 빼준 값을 result에 더해주는 방식으로 코드를 돌렸다.
그리하여
초기 코드
class Solution:
def minCost(self, colors: str, neededTime: List[int]) -> int:
leng = len(colors)
conse_lst = []
curr = colors[0]
tmp = []
for i in range(leng):
if colors[i] != curr:
curr = colors[i]
conse_lst.append(tmp)
tmp = [i]
else:
tmp.append(i)
if tmp:
conse_lst.append(tmp)
result = 0
for i in conse_lst:
if len(i) == 1:
continue
maxi = 0
subt = 0
for j in i:
subt += neededTime[j]
if neededTime[j]>maxi:
maxi = neededTime[j]
result += subt-maxi
return result그런데 효율이 아무래도 너무 안습이라 뺄 것을 빼면서 좀 더 개선을 했다.
그리고 그 결과
최종 제출
class Solution:
def minCost(self, colors: str, neededTime: List[int]) -> int:
leng = len(colors)
curr = colors[0]
start = 0
result = 0
for i in range(1,leng):
if colors[i] != curr:
curr = colors[i]
result += sum(neededTime[start:i])-max(neededTime[start:i])
start = i
if start != i:
result += sum(neededTime[start:leng])-max(neededTime[start:leng])
return result뭐 이것저것 제거해서 Runtime은 기존의 반(3110ms --> 1568ms, 70.78%)으로, 메모리는 약 12% 정도(28.7mb --> 25.1mb, 12.42%)로 줄였다. 메모리를 보았을 때 더 효율적인 방법이 있는 것 같긴 한데 이쯤만 해도 나쁘지 않다고 생각되서 더이상의 코드 개선은 stop!(메모리를 건드릴 요소가 아마도 result가 결과적으로 엄청 큰 수가 되고, 매우 잦은 변화가 있을 때 뿐일 것 같은데 그런 케이스가 있나보다.)
