[알고리즘] LeetCode 739

P

온도 리스트를 입력으로 받고, 더 따뜻한 온도가 나오기 까지 얼마나 걸리는지를 출력하는 문제.

• 입력

T = [73, 74, 75, 71, 69, 72, 76, 73]

• 출력

[1, 1, 4, 2, 1, 1, 0, 0]

S

반복

• 반복을 하긴 해야할텐데 이중 반복으로 전체 배열을 순회할 경우 시간 초과한다. 한번 반복을 하면서 값을 알아낼 수 있는 방법필요 함.
• 일단 부르트 포스 풀이

def dailyTemperatures(temp: List[int]) -> List[int]:
    result = []      
    for i in range(len(temp)):
        day = 0
        for j in range(i+1, len(temp)):
            if temp[i] < temp[j]:                 
            day = j - i                 
            break         
        result.append(day)     
return result

• 현재 값과 다음 언젠가의 값과의 비교가 필요하다. 그리고 끝까지 간 뒤에도 비었다면 0을 출력한다. 반복하면서 뭔가를 기록, 기억해둔다? 뭘? 활용할 수 있는 뭔가가 있긴 있음. 그게 뭐지. 뭐를 쓸 수 있을까. “현재값”, “더 큰값” 이 될 수 있음. 현재값을 일단 임시배열에 넣는다. 반복하면서 더 큰게 아니면 또 넣는다. 더 큰 값이 나오면 배열을 반복하면서 차이를 결과 배열에 넣는다. 임시배열은 앞이 가장 크고 작아지는 순서를 갖는다. 왜냐면 그렇지 않다면 배열에 들어갈 수 없기 때문이다. 더 큰 수를 아직 못만난 배열 temp, 결과 배열 result 를 준비한다. 어디에 넣을지 알려면 자릿수가 필요 하다. temp 배열은 순서대로 쭉 들어가는게 아니라 조건에 맞을 경우 pop 되는 등 변경되기 때문에 순차적으로 result 를 채워넣는 게 아니다. 일단 0으로 입력 배열의 길이만큼 채워둔다.

for i in T:
    result.append(0)

result 배열에 넣을 ‘값’과 ‘자릿수’ 를 명확히 하기 위해 temp 배열의 구조를 [{value: 'value', index: 'index'}] 와 같이 사용하려 했다. 그런데 생각해보니 index 만으로 값을 조회할 수 있다.

여기까지 나온 것으로 코드 작성

temp = []
result = []
for i in T:
    result.append(0)
for i in range(len(T)):
    # temp 가 비어있는 경우 -> 뒤쪽으로 뺌
# temp 와 비교 시도
		# 조건을 걸고 필요한 데이터 추출
		while len(temp) > 0 and temp[-1] < T[i]:
        result[temp[-1]] = i - temp[-1]
        temp.pop()
		# 현재 값은 temp 에 넣는다.
    temp.append(i)
# 여기에서 temp 에 아직 값이 존재할 수 있으나 그것은 더 큰 값을 못찾았기 때문이므로 0으로 처리 됨.
# result 를 0으로 채워뒀으므로 그대로 둘 수 있음
return result

A

def daily_temperatures(T: List[int]) -> List[int]:
    temp = []
    result = []
for i in T:
        result.append(0)
for i in range(len(T)):
        while len(temp) > 0 and T[temp[-1]] < T[i]:
            result[temp[-1]] = i - temp[-1]
            temp.pop()
temp.append(i)
return result

• 책에 나온 풀이가 확실히 깔끔하다.

def dailyTemperatures(self, T: List[int]) -> List[int]:
    answer = [0] * len(T)
    stack = []
    for i, cur in enumerate(T):
        last = stack.pop()
        answer[last] = i - last
    stack.append(i)
    return answer