백준 자바 1874 스택 시퀀스

쌓이는 순서 문제… 시간이 많이 걸렸어요! 그런데 Arraylist만으로 풀 수 있는 문제… Arraylist를 쓸 생각 없이 계속 Stack만으로 풀려고 하다 보니 시간이 오래 걸렸습니다.

package boj_basic.cp_1;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;

public class Q1874 {

    public static void main(String() args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());

        int a = 0;
        int c = 0;

        Stack<Integer> stack = new Stack<>();

        for(int i = 0; i < n; i++) {
            int num = Integer.parseInt(br.readLine());
            if(a<num) {
                for(int b=a+1 ; b <=num; b++) {
                    stack.push(b);
                    bw.write("+\n");
                    a=stack.peek();
                }
            }
            else {
                if(!stack.isEmpty()) {
                    if(c!=num) {
                        // "NO"를 출력하지 않고 바로 종료하지 않음
                        break;
                    }
                    else {
                        for(int d = c; d>=num; d--) {
                            stack.pop();
                            if(!stack.isEmpty())
                                c=stack.peek();
                            bw.write("-\n");
                        }
                        continue;
                    }
                }
            }
            if(!stack.isEmpty()) {
                stack.pop();
                if(!stack.isEmpty())
                    c=stack.peek();
                bw.write("-\n");
            }
        }

        // 입력이 끝나고 스택이 비어있지 않은 경우에 "NO"를 출력
        if(!stack.isEmpty()) {
            bw.write("NO\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

제가 처음에 작성한 코드입니다. 예제 출력 1은 잘 되는데 순서가 안맞아서 예제 출력 2에서는 “NO”만 나와야 +나 – 출력이 나오지만 + – + – + + + – NO 출력은 그런 식이었습니다. 배열리스트 쓸 생각도 못하고 그냥 스택으로 해결하려다보니…^^

그래서 arraylist를 사용하여 +와 -를 별도로 설정하고 마지막에 스택이 비어 있지 않은 경우에만 NO를 출력하도록 코드를 수정했습니다.

package boj_basic.cp_1;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Stack;

public class Q1874_1 {

    public static void main(String() args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());

        int a = 0;
        int c = 0;

        Stack<Integer> stack = new Stack<>();
        ArrayList<String> array = new ArrayList<>();

        for(int i = 0; i < n; i++) {
            int num = Integer.parseInt(br.readLine());
            
            if(a<num) {
                for(int b=a+1 ; b <=num; b++) {
                    stack.push(b); //1234 집어넣음
                    array.add("+\n"); //arraylist에 1234 ++++
                    a=stack.peek();  // a=4
                }
            }
            else { //(a>=num) 3이 들어왔을 때 a인 4가 3보다 크니까
                if(!stack.isEmpty()) {
                    if(c!=num)  //만약 들어온 num값과 제일 위에 있는 값이 동일하지 않다면 수열을 만들 수가 없음.
                        break; //  for(int i = 0; i < n; i++) 반복문 빠져나옴
                    else {
                    	stack.pop();
                    	if(!stack.isEmpty())
                    		c=stack.peek(); //c=2
                    	array.add("-\n");
                    	continue; //continue해서 밑에 if문 실행하지 않고 바로 위에 for문으로 올라가서 continue!
                    }
                }
            }
            
            
            if(!stack.isEmpty()) { //for문 한 번 돌릴때마다 마지막에 pop을 한번씩! (사실은 위에 if문 만족할 때만 행해지는 if문임)
                stack.pop();
                if(!stack.isEmpty())
                    c=stack.peek(); // c=3
                array.add("-\n");
            }
        }

        // 입력이 끝나고 스택이 비어있지 않은 경우에 "NO"를 출력
        if(!stack.isEmpty()) {
            bw.write("NO\n");
        }
        else {
        	for(String st : array) {
        		bw.write(st);
        	}
        }

        bw.flush();
        bw.close();
        br.close();
    }

}

성공적인.

package boj_basic.cp_1;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Stack;

public class Q1874_2 {

	public static void main(String() args) throws NumberFormatException, IOException {
		 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	     BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	        
	        int n = Integer.parseInt(br.readLine());
	        
	        Stack<Integer>stack = new Stack<>();
	        
	        int() arr = new int(n);
	        
	        ArrayList<String> array = new ArrayList<>();
	        
	        int index = 0;
	        
	        for(int i = 0; i<n; i++) {
	        	int num = Integer.parseInt(br.readLine());
	        	arr(i)=num;
	        }
	        
	        for(int i = 1; i<=n; i++) {
	        	stack.push(i);
	        	array.add("+\n");
	        	while(!stack.isEmpty()) {
	        		if(stack.peek()==arr(index)) {
	        			stack.pop();
	        			array.add("-\n");
	        			index++;
	        		}
	        		else 
	        			break;
	        	}
	        }
	        
	        if(!stack.isEmpty()) {
	        	bw.write("NO");
	        }
	        else {
	        	for(String st : array)
	        		bw.write(st);
	        }
	        
	        bw.flush();
	        bw.close();
	        br.close();

	}

}

남의 코드를 참고하면 깔끔한 코드 완성!!

시간과 메모리가 모두 줄어드는 것을 볼 수 있습니다!