스택
스택 의 핵심 이론
삽입과 삭제 연산이 LIFO (Last-In First-Out) 으로 이루어지는 자료구조
삽입과 삭제가 한쪽(top)에서만 일어난다.
- DFS(깊이 우선 탐색), 백트래킹 에 효과적
- 재귀 함수 알고리즘의 원리와 일맥상통
JAVA 에서 제공하는 Stack
클래스
- 수식 계산, 수식괄호검사 ,워드프로세서의 undo/redo, 웹브라우저의 뒤로/앞으로
Stack<> stack = new Stack<>();
// java.util.Stack
/**
The Stack class represents a last-in-first-out (LIFO) stack of objects.
It extends class Vector with five operations that allow a vector to be treated as a stack.
The usual push and pop operations are provided,
as well as a method to peek at the top item on the stack,
a method to test for whether the stack is empty,
and a method to search the stack for an item and discover how far it is from the top.
When a stack is first created, it contains no items.
**/
잘못 생각한 수도코드
처음 생각 : 모든 케이스 가능
stack에 넣을 때, 순서를 바꿔서 넣을 수 있다고 생각함.
수도 코드 1<2 input[last] < next input 이면 stack {1,5 } stack에 push input[] last ~ 0 까지 넣어 (작은 값부터) stack에서 출력 out={5,1} 2<5 stack {2} out={5,1,2} 3<4 stack ={3,5}
두번째 : 불가능한 케이스를 생각하지 못함
int n; // 1~n까지 오름차순으로 넣음 int start=1 ArrayList<> input; int next=st.nextInt; if(input.empty||input.peek>next){ input.push(next); //6 } if(input.peek<next){// next=6 input={4,3} for(int i =start;i<=input[0]){ // i=1; i<=4 stack.push(i) // stack={1,2,3,4} result.append("+") } start=input.peek+1; // start= 7 for(!input.empty){ stack.pop() // stack={1,2,5} result.append("-") input.pop() //input={} } }
3번째 - 안됨
int start=1; input={4 3 6 8 7 5 2 1}; int max = input[0]; for(int i =0;i<n;i++){ if(input[i]>input[i+1]){ // 4,3 / 8,7,5,2,1 if(i+1==n-1){ for(int j=start; j<=max;j++){ j=7, j<=8 stack.push(j); // stack={1,2,5,7,8} } while(stack.peek>=input[i]){ // 8>=8 stack.pop(); // stack={1,2,5,7} } } } if(input[i]<input[i+1]){ // 3<6 6<8 for(int j=start;j<=max;j++){ // j=1, j<=4 / j=5 j<=6 stack.push(j); // stack={1,2,3,4} / stack={1,2,5,6} } while(stack.peek>=input[i]){ //4>=3 3>=3 2<3 / 6>=6 5<6 stack.pop(); //stack={1,2,3} stack={1,2} / stack={1,2,5} } start=max+1; // start=5; / start=7; max=input[i+1]; // max=6; / max=8; } } int n; // 1~n까지 오름차순으로 넣음 int start=1 ArrayList<> input; int next=st.nextInt; if(input.empty||input.peek>next){ input.push(next); //6 } if(input.peek<next){// next=6 input={4,3} for(int i =start;i<=input[0]){ // i=1; i<=4 stack.push(i) // stack={1,2,3,4} result.append("+") } start=input.peek+1; // start= 7 for(!input.empty){ stack.pop() // stack={1,2,5} result.append("-") input.pop() //input={} } }
1차 시도 - 실패
수도코드
int start=1; input={1,2,5,3,4}; int max = 0 // for(int i =0;i<n-1;i++){ if(input[i]>input[i+1]){ // 5>3 if(i+1==n-1){ for(int j=start; j<=input[max];j++){ stack.push(j); while(stack.peek>=input[i]){ stack.pop(); } } } if(input[i]<input[i+1]){ // 1<2 // 2<5 // 3<4 for(int j=start;j<=input[max];j++){ j=1;j<=1 // j=2;j<=2 // j=3;j<=5 stack.push(j); // stack={1} // stack={2} // stack={3,4,5} } // i=3, input[i]=3, max=2, input[max]=5 for(int j=max;j<=i;j++){ // j=2, j<=3 if(input[j]== stack.peek) // 5==5 3!=4 stack.pop(); // stack={3,4} } start=input[max]+1; // start=2 // start=3 // start=5+1=6 max=i+1; // input[1]=2 // input[2]=5 // max=4, input[4]=4 } } if(!stack.isEmpty) sout(no)
소스 코드
100% 까지 간다음에 틀렸습니다. 나옴.
input[] 의 마지막 값을 고려하지 않아서 생기는 케이스인 것 같아 추후 리팩토링 해보면 좋을 것 같음.
import java.io.*; import java.util.ArrayList; import java.util.Stack; public class Main { static int [] input; static Stack<Integer> stack = new Stack<>(); public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); StringBuilder sb = new StringBuilder(); // input 값 받기 input = new int[n]; for(int i =0;i<n;i++){ input[i]=Integer.parseInt(br.readLine()); } int start=1; int max=0; for(int i=0;i<n-1;i++){ // 다음값보다 크면 넘어가 if(input[i]>input[i+1]){ // i+1 이 마지막 값일 때 if(i==n-2){ cal(i+1, start, max, sb); } } else{ cal(i,start,max,sb); start=input[max]+1; max=i+1; } } if(!stack.isEmpty()){ System.out.println("NO"); }else{ System.out.println(sb.toString()); } br.close(); } public static void cal(int i, int start, int max, StringBuilder sb) { for(int j=start;j<=input[max];j++){ stack.push(j); sb.append("+").append("\n"); } for(int j=max;j<=i;j++){ if(input[j]== stack.peek()){ stack.pop(); sb.append("-").append("\n"); } } } }
2차 시도 - 34908kb 2600ms
stack.contains(input)
을 하여 input을 가지고 있지만 peek가 아닌 경우를 invalid로 빼주었는데,
이부분에서 시간이 오래 소요되는 것 같다. (매번 stack의 모든 요소를 검사하니)
소스코드
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; public class Main { static Stack<Integer> stack = new Stack<>(); public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); StringBuilder sb = new StringBuilder(); boolean invalid=false; int input; int end=0; for (int i = 0; i < n; i++) { input = Integer.parseInt(br.readLine()); if(stack.contains(input)){ if(stack.peek()==input){ stack.pop(); sb.append("-").append("\n"); }else{ invalid=true; break; } }else{ for(int num=end+1;num<=input;num++){ stack.push(num); sb.append("+").append("\n"); } end=input; stack.pop(); sb.append("-").append("\n"); } } if (invalid) { System.out.println("NO"); } else { System.out.println(sb.toString()); } br.close(); } }
3차 시도 - 27804kb 368ms
2차시도에서 고려했던 contains()
를 빼고
num 값이 end+1 보다 작게 되는 경우
를 invalid로 수정하였다.
ex) 1,2,5,3,4 예제에서 input=3일때, num=3 인데, end+1=6 이므로 불가능하게 된다.
소스 코드
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; public class Main { static Stack<Integer> stack = new Stack<>(); public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); StringBuilder sb = new StringBuilder(); boolean invalid=false; int input; int end=0; for (int i = 0; i < n; i++) { input = Integer.parseInt(br.readLine()); if (!stack.isEmpty()&&stack.peek() == input) { stack.pop(); sb.append("-").append("\n"); } else { if (end + 1 > input) { invalid = true; break; } for (int num = end + 1; num <= input; num++) { stack.push(num); sb.append("+").append("\n"); } end = input; stack.pop(); sb.append("-").append("\n"); } } if (invalid) { System.out.println("NO"); } else { System.out.println(sb.toString()); } br.close(); } }