[알고리즘] Daily temperatures (java 풀이)

문제

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

 

번역

일일 온도 T의 목록이 주어지면, 주어진 날짜에 대해 더 따뜻한 온도가 될 때까지 기다려야하는 일 수를 알려주는 리스트를 반환하세요. 더이상 따뜻해질 날이 없으면 0을 리턴하세요.

 

 

example01

static int[] arr = { 19, 20, 20, 19, 19, 30 };
ans = 1 4 3 2 1 0

example02

static int [] nums = {73,74,75,71,69,72,76,73};
ans = 1 1 4 2 1 1 0 0 

 

 

풀이1 (2중 for문 이용 - 비효율)

import java.util.ArrayList;
import java.util.Stack;

public class Daily_Temperature {

	static int[] arr = { 19, 20, 20, 19, 19, 30 };
	
	public static void main(String[] args) {
		Stack<Integer> stack = new Stack<>();
		ArrayList<Integer> list = new ArrayList<>();

		for (int i = 0; i < arr.length - 1; i++) {
			if (stack.empty()) {
				stack.add(i);
			}

			for (int j = i + 1; j < arr.length; j++) {

				if (arr[i] < arr[j]) {
					list.add(j - stack.pop());
					break;
				}

				if (j == arr.length - 1) {
					list.add(0);
				}

			}

		}
		list.add(0);
		for (int res : list) {
			System.out.print(res + " ");
		}
	}

}

 

풀이2 

import java.util.Stack;

public class Daily_Temperature2 {
	static int[] nums = { 73, 74, 75, 71, 69, 72, 76, 73 };

	public static void main(String[] args) {
		Stack<Integer> st = new Stack<>();

		int[] res = new int[nums.length];

		for (int i = 0; i < nums.length; i++) {
			while (!st.isEmpty() && nums[st.peek()] < nums[i]) {
				res[st.peek()] = i - st.pop();
			}

			st.push(i);
		}

		for (int r : res) {
			System.out.print(r + " ");
		}

	}

}