본문 바로가기
자료구조와 알고리즘/알고리즘

[Boj 1874] 스택 수열

by 김yejin 2022. 8. 24.

 

 

스택

 

스택 의 핵심 이론

삽입과 삭제 연산이 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();
        }
    
    
    }