현재의 온도보다 미래의 온도가 더 높아지려면 며칠 남았는지 계산하는 문제이다.(날이 따뜻해지기만을 바라는 나같다..)
처음에 이중 포인터를 사용해서 풀이 했다가 시간 초과 에러가 발생하였다.
문제 설명
포인터는 현재의 값 바로 다음 값을 가리키도록 초기화한다. (포인터는 어차피 미래의 값만 가리키면 된다.) 포인터를 증가시켜 나가며 현재의 값(cur)이 가리키는 값과 포인터(pointer)가 가리키는 값을 비교한다. 포인터가 가리키는 값(미래의 온도)이 더 크다면 pointer와 cur의 차이(앞으로 몇일 남았는지)를 이용해 결과 배열에 넣어준다.
이 때 미래에 더 높은 온도가 남았는지 볼 필요는 없기 때문에 바로 cur 인덱스를 증가시켜주고, 포인터도 cur 인덱스 다음으로 설정해준다.
이 때 포인터가 온도 배열의 끝에 다다랐을 경우(미래에 더 높은 온도가 없을 경우) cur이 가리키는 값을 다음날의 온도로 옮긴다.
이 과정을 온도 배열의 모든 요소에 적용시키는 방법으로 문제를 풀었었다. 하지만 시간 초과 에러가 발생하였고..
temperatures = [73,74,75,71,69,72,76,73]
output = [0 for _ in range(len(temperatures))]
cur = 0
pointer = cur + 1
while cur < len(temperatures) - 1:
if temperatures[cur] < temperatures[pointer]:
output[cur] = pointer - cur
cur += 1
pointer = cur + 1
else:
pointer += 1
if pointer > len(temperatures) - 1:
cur += 1
pointer = cur + 1
print(output) 이 방법 말고는 모르겠어서 고민 끝에 결국 정답을 찾아보게 되었지만..
정답 코드를 이해하는 데 너무 오래 걸려서 꼭 정리를 해야겠다고 생각했다.
temps = [73,74,75,71,69,72,76,73]
output = [0 for _ in range(len(temps))]
stack = []
for idx, temp in enumerate(temps):
while len(stack) > 0 and temp > temps[stack[-1]]:
last = stack.pop()
output[last] = idx - last
stack.append(idx)
print(output)
풀이 설명
그러니까, 이때 현재 온도라는 것은 위에서와 반대 개념인 것이다.
이때의 '현재'는 스택에 쌓여있는 인덱스가 가리키는 시점보다 미래인 것이다.
온도 배열을 순회하면서 스택에 인덱스를 넣는다.
스택에 뭔가가 들어있을 때,
현재 온도가 스택에 들어있는 최근(가장 나중에 넣은)값(pop한 결과)인 인덱스가 가리키고 있는 온도보다 높을 경우(따뜻), 결과 배열의 인덱스(스택에서 꺼낸 인덱스. 즉, 상대적으로 과거의 날짜)가 가리키는 위치에 현재 온도를 가리키는 인덱스와 스택에서 꺼낸 그 인덱스의 차(날짜 차이)를 넣는다.
이를 배열의 끝에 다다랐을 때까지 반복하면 된다.
