[LeetCode- Ch3. 배열] 2. 일일 온도 # (+ arr+stack)

https://leetcode.com/problems/daily-temperatures/submissions/

Daily Temperatures - LeetCode

 

1. 이중 For문 이용 : 타임리밋 발생

 

2. for+while문: 타임리밋 발생

: 더 높은 온도 찾을 때 까지 while문으로 반복

 

 

3. 스택이용

: 스택에 배열의 인덱스를 넣고, 배열을 돌면서 인덱스간 차이를 이용

 

1. 이중 for문 이용

import java.util.*;
class Solution {
    public int[] dailyTemperatures(int[] arr) {
        //더 따듯한 날씨의 날을 얻기 위해 기다려야하는 날짜의 수
        //더 따뜻한 날이 오지 않으면 0리턴
        int n=arr.length;
        int tmp=Integer.MIN_VALUE;
        int[] answer= new int[n];
        for(int i=0;i<n;i++){
            for(int j=i+1; j<=n; j++){
                if(j==n) answer[i]=0;
                else if(arr[j]>arr[i]){
                    //6-2 =4
                    //(n-2) - 2 
                    answer[i]=j-i;
                    break;
                }
            }
        }
        return answer;
    }
}

-> 타임 리밋 발생

 

2. for+while문

class Solution {
    public int[] dailyTemperatures(int[] tem) {
		int len = tem.length;
		int[] result = new int[len];
		int max = 0;

		for (int i = 0; i < len; i++) {
			max = i;
			//System.out.println("max " + max);
			while (max <= len - 1 && tem[i] >= tem[max]) {
				max++;
			}
			if (max <= len - 1)
				result[i] = max - i;
			else
				result[i] = 0;
		}
		return result;
	}
}

-> 타임 리밋 발생

 

3. 스택 이용

class Solution {
    public int[] dailyTemperatures(int[] arr) {
        int n=arr.length;
        Stack<Integer> stack = new Stack<>();
        int[] answer= new int[n];
        //온도가 아닌 인덱스를 넣고 비교한다.
        //: 스택이 비지 않았을 때, 맨 위 값이 인덱스보다 더 클 때까지 반복해서 넣는다.
        //-> 그 외엔 인덱스를 넣는다.
        for(int i=0;i<n;i++){
            //73 -> 74
            //peek: 0
            
            //74-> 75
            //peek: 1
            
            //75-> 71 -> 69까지 스택에 쌓인다.
            //peek: 4
            
            //75-> 71인 상태에서 2번째 반복
            
            //75 -> 72인 상태
            
            while(!stack.isEmpty() && arr[stack.peek()]<arr[i]){
                //arr[0]<arr[1]일 경우
                //arr[1]<arr[2]일 경우
                //arr[4]<arr[5]일 경우
                //arr[3]<arr[5]일 경우
                //arr[2]<arr[6]인 경우
                int index= stack.pop();
                //0
                //1
                //4
                //3
                //2
                
                answer[index]=i-index;
                //answer[0]=1-0=1
                //answer[1]=2-1=1
                //answer[5]=6-5=1
                //answer[4]=5-4=1
                //answer[3]=5-3=2
                //answer[2]=6-2=4
                
                //141211 [00] : arr[stack.peek()]<arr[i]인 경우가 존재하지 않음.
            }
            
            stack.push(i);
        }
        return answer;
    }
}

---

class Solution {
    public int[] dailyTemperatures(int[] arr) {
        //일일온도 최댓값
        //존재하지 않으면 0 리턴
        int n=arr.length;
        int[] answer=new int[n];
        //j-i 리턴
        for(int i=0; i<n;i++){
            for(int j=i+1; j<n;j++){
                if(arr[j]>arr[i]) {
                    answer[i]=j-i;
                    break;
                }
            }
        }
        return answer;
    }
}

-> 타임 리밋 발생

 

#스택활용

class Solution {
    public int[] dailyTemperatures(int[] tem) {
		int n = tem.length;
		int[] result = new int[n];
        Stack<Integer> stack = new Stack<>();
		for(int i=0;i<n;i++){
            while(!stack.isEmpty() && tem[stack.peek()]<tem[i]){
                int index=stack.pop();
                result[index]=i-index;
            }
            stack.push(i);
        }
        
		return result;
	}
}