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

[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();
    }


}

 

 

 
 

 

저작자표시 (새창열림)

티스토리툴바