더 따뜻한 날까지의 거리

자바스크립트 코딩테스트 문제로 monotonic-stack 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.

today medium monotonic-stack 함수명: solution 제한 시간: 200ms

정수 배열 temperatures가 주어질 때, 각 날마다 자신보다 더 따뜻한 날이 몇 일 뒤에 오는지를 담은 배열을 반환하는 solution 함수를 작성하세요. 이후에 더 따뜻한 날이 없다면 그 자리는 0이어야 합니다.

제한사항

temperatures의 길이는 1 이상 100,000 이하입니다.
각 원소는 -50 이상 100 이하의 정수입니다.
같은 온도는 더 따뜻한 날로 취급하지 않습니다.
반환 배열의 길이는 입력 배열의 길이와 같아야 합니다.

예시

입력: [18, 21, 19, 22, 20, 25] → 출력: [1, 2, 1, 2, 1, 0]
입력: [30, 29, 28, 27] → 출력: [0, 0, 0, 0]
입력: [15, 15, 16, 15, 17] → 출력: [2, 1, 2, 1, 0]

힌트

각 위치에서 오른쪽을 끝까지 매번 다시 보면 느립니다.
아직 더 따뜻한 날을 못 찾은 인덱스들을 따로 모아 두면, 새 온도를 만났을 때 여러 답을 한꺼번에 갱신할 수 있습니다.
현재 온도가 스택 맨 위 인덱스의 온도보다 클 때만 답이 확정됩니다.

해설

이 문제는 각 인덱스마다 오른쪽에서 처음 등장하는 더 큰 값을 찾는 문제입니다.

가장 단순한 방법은 각 날마다 뒤쪽을 전부 확인하는 것이지만, 그러면 최악의 경우 O(n^2)이 됩니다. 입력 길이가 최대 100,000이므로 비효율적입니다.

효율적으로 풀기 위해 아직 답이 정해지지 않은 인덱스를 스택에 넣어 관리할 수 있습니다.

동작 방식은 다음과 같습니다.

결과 배열을 모두 0으로 초기화합니다.
배열을 왼쪽부터 순회합니다.
현재 온도가 스택 맨 위 인덱스의 온도보다 크다면,
- 그 인덱스는 지금 처음으로 더 따뜻한 날을 만난 것입니다.
- 결과값은 현재 인덱스 - 이전 인덱스가 됩니다.
- 조건이 만족하는 동안 스택에서 계속 꺼냅니다.
현재 인덱스를 스택에 넣습니다.
끝까지 순회한 뒤에도 스택에 남은 인덱스는 더 따뜻한 날이 없으므로 0 그대로 둡니다.

예를 들어 [18, 21, 19, 22, 20, 25]를 보면:

18은 다음 날 21을 만나므로 1
21은 두 칸 뒤 22를 만나므로 2
19는 다음 따뜻한 날 22까지 1
22는 25까지 2
20은 25까지 1
25는 이후가 없으므로 0

이 방식은 각 인덱스가 스택에 한 번 들어가고 한 번만 나오므로 전체 시간 복잡도는 O(n)입니다. 배열을 한 번만 훑으면서도 정답을 구할 수 있어 중급 난이도의 대표적인 스택 응용 문제로 볼 수 있습니다.

코드 작성

starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.

JavaScript 에디터 로딩 중...

커스텀 테스트

함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]

아직 실행하지 않았습니다.

실행 결과

아직 실행하지 않았습니다.

예제 테스트를 실행하면 여기에서 결과를 확인할 수 있습니다.

댓글

문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.