-개발환경-
| IDE : Eclipse IDE for Java Developers Version: 2020-03 (4.15.0) 공부 자료 : www.inflearn.com/course/%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EC%9E%90%EB%B0%94/lecture/22652 |
-문제-
날마다의 온도모음 리스트가 주어 진다. 그 리스트를 통해 당신은 더 따뜻한 날까지 몇일을 기다려야하는지
알수 있다, 각각의 날에 대해 몇일을 기다리면 온도가 더 따뜻해지는지를 리스트로 반환하라.
적합한 날이 없다면 , 0을 넣어 반환하라.
ex)
T = [73, 74, 75, 71, 69, 72, 76, 73],
your output should be [1, 1, 4, 2, 1, 1, 0, 0].
Note) 측정온도의 갯수는 [1,30000] 이다.
온도의 범위는 [30,100] 이며 정수이다.
-접근법-
윗 개념 +
for 문을 이용하여 nums 원소에 하나씩 접근할 시 , 문제해결을 위해서
반드시 역행하는 순서가 필요하게 되므로 스택을 이용.
-DailyTemperature.java-
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
package codingTest;
import java.util.Stack;
public class DailyTemperature {
public static void main(String[] args) {
int[] nums= {73,74,75,71,69,72,76,73};
int[] res = solve(nums);
//outPut
for(int i : res) {
System.out.print(i+" ");
}
}
public static int[] solve(int[] temper) {
//1. ds
Stack<Integer> stack=new Stack<>();
int[] result=new int[temper.length];
//2. for,while + algo
for(int i=0; i<temper.length;i++) {
System.out.println("==================================");
System.out.println("temper(온도): "+temper[i]);//test
while(!stack.isEmpty() && temper[stack.peek()] <temper[i] ) {
//====================test begin=======================
Stack<Integer> stemp=new Stack<>();//test
stemp=(Stack<Integer>) stack.clone();//test
System.out.print("맨 위-> 맨아래 순 stack: ");
while(!stemp.isEmpty()) {//test while
System.out.print(stemp.pop()+" ");
}
System.out.println();//test
//====================test end=======================
int index=stack.pop();
//====================test begin=======================
System.out.println("i : "+i+" index : "+index);//test
//====================test end=======================
result[index]= i-index;
//====================test begin=======================
stemp=(Stack<Integer>) stack.clone();//test
System.out.print("맨 위-> 맨아래 순 stack: ");//test
while(!stemp.isEmpty()) {//test while
System.out.print(stemp.pop()+" ");
}
System.out.println();//test
//====================test end=======================
}
stack.push(i);
}
return result;
}
}
|
cs |
-Description
18 : 온도의 인덱스를 값으로 하는 stack 생성
19 : 결과를 담을 result 배열 생성
26 : 스택에 데이터가 있고 , 온도[스택의 꼭대기 값] < 온도[i] 을 만족하면 반복문 수행
38 : index에 스택의 peek 데이터 삽입, 그리고 pop.
44 : 접근법 이미지에서 설명한 내용
56 : for 문 내부의 끝에서 stack 온도 i를 삽입
58 : 배열 result 반환
개념이해가 어려워서 직접 데이터의 흐름에 따라 아래와 같이 작성해보았다.
-추가개념-
Stack
//필요선언문
import java.util.Stack;
//객체생성
Stack<지네릭스> stack=new Stack<>()
//관련함수
stack.isEmpty() // 비어있으면 true반환 그외엔 false반환
stack.pop() // 꼭대기값을 pop함과 동시에 데이터 반환
stack.peek() // 단순 꼭대기 값을 반환
stack.push(값); // 값을 stack에 삽입
-마침글-
브루트 포스 방식으로 스택문제에 접근하면 낭패를 볼 수 있다고 생각하게 되었다.
스택만의 유형에 익숙해질 필요가 있다.
인용
'21년이전 > 자바-Algorithm' 카테고리의 다른 글
| TwoSum (0) | 2021.03.22 |
|---|---|
| MoveZeros (0) | 2021.03.21 |
| MeetingRoom (0) | 2021.03.20 |
