-
-
Save tae0y/1ee91a0fc0332815a1256bf0bb064dd9 to your computer and use it in GitHub Desktop.
import java.util.ArrayDeque; | |
import java.util.ArrayList; | |
import java.util.Deque; | |
import java.util.Stack; | |
/** | |
* 2020-06-14 by solar-beam | |
* https://programmers.co.kr/learn/courses/30/lessons/42588?language=java | |
* 스택/큐 연습문제, 신호는 왼쪽으로만 보낼 수 있다 | |
* */ | |
public class Main { | |
public static void main(String[] args) { | |
int[] case1 = {6,9,5,7,4}; solution(case1); | |
int[] case2 = {3,9,9,3,5,7,2}; solution(case2); | |
int[] case3 = {1,5,3,6,7,6,5}; solution(case3); | |
} | |
public static int[] solution(int[] heights){ | |
int[] answer = new int[heights.length]; | |
//brute-force | |
int bf_cnt1 = 0, bf_cnt2=0; | |
for(int i=0; i<heights.length; i++){ | |
bf_cnt1++; | |
for(int j=i; j>=0; j--){ | |
bf_cnt2++; | |
if(heights[j]>heights[i]){ | |
answer[i]=j+1; | |
break; | |
} | |
} | |
} | |
//스택에 담아놨다가 자신보다 큰 탑을 만나면 쏟아놓기 | |
// * 불변식 : 스택에는 연속하여 작아지는 값들만 입력한다. | |
Stack<Integer> cheat = new Stack(); | |
int st_cnt1=0, st_cnt2=0, st_cnt3=0; | |
for(int i = heights.length-1; i>0; i--){ | |
//스택이 비어있다 | |
//스택이 차있는데 PICK해보니 크거나 같다 | |
//스택이 차있는데 PICK해보니 작다 | |
st_cnt1++; | |
while(!cheat.isEmpty()){ | |
st_cnt2++; | |
if(heights[cheat.peek()]>=heights[i]) break; | |
st_cnt3++; | |
answer[cheat.peek()] = i+1; | |
cheat.pop(); | |
} | |
cheat.push(i); | |
} | |
//빠른스택 Deque : http://tcpschool.com/java/java_collectionFramework_stackQueue | |
//직접구현 : https://donghoson.tistory.com/150 | |
MyStack cheat2 = new MyStack(); | |
int mst_cnt1=0, mst_cnt2=0, mst_cnt3=0; | |
for(int i = heights.length-1; i>0; i--) { | |
//스택이 비어있다 | |
//스택이 차있는데 PICK해보니 크거나 같다 | |
//스택이 차있는데 PICK해보니 작다 | |
mst_cnt1++; | |
while (!cheat2.isEmpty()) { | |
mst_cnt2++; | |
if (heights[cheat2.peek()] >= heights[i]) break; | |
mst_cnt3++; | |
answer[cheat2.peek()] = i + 1; | |
cheat2.pop(); | |
} | |
cheat2.push(i); | |
} | |
//질문 | |
// 큐 검색시간(log M), 큐 구현시간(n log N), 정렬된 자료구조 | |
// 힙과 스택은 왜 다른가 | |
//for(int i=0; i<answer.length; i++) System.out.print(answer[i]+" "); | |
//System.out.println(); | |
System.out.println("brute force : 외부for("+bf_cnt1+"), 내부for("+bf_cnt2+")"); | |
System.out.println("stack STL : for("+st_cnt1+"), while("+st_cnt2+"), while 內 if 이하("+st_cnt3+")"); | |
System.out.println("stack my own : for("+mst_cnt1+"), while("+mst_cnt2+"), while 內 if 이하("+mst_cnt3+")"); | |
return answer; | |
} | |
private static class MyStack { | |
int[] data; | |
int pos; | |
int size; | |
MyStack(){ | |
data = new int[1000]; | |
pos = -1; | |
size = 1000; | |
} | |
MyStack(int stack_size){ | |
data = new int[stack_size]; | |
pos = -1; | |
size = stack_size; | |
} | |
boolean isEmpty(){ | |
return pos<0; | |
} | |
int peek(){ | |
if(isEmpty()) return -1; | |
return data[pos]; | |
} | |
int pop(){ | |
if(isEmpty()) return -1; | |
return data[pos--]; | |
} | |
int push(int e){ | |
if(pos+1<size) data[++pos] = e; | |
return e; | |
} | |
} | |
} |
with stack(arraylist)
테스트 1 〉 | 통과 (1.45ms, 54.5MB)
테스트 2 〉 | 실패 (2.83ms, 50.2MB)
테스트 3 〉 | 통과 (1.53ms, 52.4MB)
테스트 4 〉 | 실패 (2.89ms, 50MB)
테스트 5 〉 | 통과 (1.49ms, 50.4MB)
테스트 6 〉 | 실패 (3.24ms, 50.1MB)
테스트 7 〉 | 통과 (1.43ms, 51.9MB)
테스트 8 〉 | 통과 (1.40ms, 49.9MB)
with stack, arraydeque, mystack
테스트 1 〉 | 통과 (1.51ms, 52.7MB)
테스트 2 〉 | 실패 (2.74ms, 52.3MB)
테스트 3 〉 | 통과 (1.53ms, 52.6MB)
테스트 4 〉 | 실패 (2.88ms, 50.7MB)
테스트 5 〉 | 통과 (1.74ms, 52.9MB)
테스트 6 〉 | 실패 (2.88ms, 52.8MB)
테스트 7 〉 | 통과 (1.54ms, 54.4MB)
테스트 8 〉 | 통과 (1.54ms, 52.5MB)
#1
brute force : 외부for(5), 내부for(10)
stack STL : for(4), while(4), while 內 if 이하(3)
stack my own : for(4), while(4), while 內 if 이하(3)
#2
brute force : 외부for(7), 내부for(17)
stack STL : for(6), while(7), while 內 if 이하(4)
stack my own : for(6), while(7), while 內 if 이하(4)
#3
brute force : 외부for(7), 내부for(18)
stack STL : for(6), while(6), while 內 if 이하(3)
stack my own : for(6), while(6), while 內 if 이하(3)
brute-force
테스트 1 〉 | 통과 (1.59ms, 50.2MB)
테스트 2 〉 | 통과 (1.49ms, 52.6MB)
테스트 3 〉 | 통과 (1.58ms, 50.3MB)
테스트 4 〉 | 통과 (1.43ms, 52.7MB)
테스트 5 〉 | 통과 (1.58ms, 52.9MB)
테스트 6 〉 | 통과 (1.41ms, 53.4MB)
테스트 7 〉 | 통과 (1.41ms, 51MB)
테스트 8 〉 | 통과 (1.41ms, 52.3MB)