[백준] no1874. 스택수열

문제

: https://www.acmicpc.net/problem/1874

---

시도 1

: 되긴 하는데 메모리 초과 ㅋㅋㅋㅋㅋ

1. 입력을 싹다 queue에 넣고, stack1에 T부터 1까지 넣어놓고, Stack2에 옮겨 담아가며 비교

2. queue가 남았는데, Stack1에서 다 빠지면, Stack2에 있는거로 다시 비교

3. 비교중 queue의 첫번째와 Stack2가 다르면 "No" 출력

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class no1874 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        Stack<Integer> stack1 = new Stack<>();
        Queue<Integer> queue = new LinkedList<>();
        Stack<Integer> stack2 = new Stack<>();

        for (int i = T; i > 0; i--) {
            stack1.push(i);
            queue.add(Integer.valueOf(br.readLine()));
        }
        queue.add(0);
        String output = "";

        while (queue.peek() != 0) {
            if (!stack1.empty()) {
                if(!stack2.empty() && stack2.peek().equals(queue.peek())) {
                    queue.poll();
                    stack2.pop();
                    output += "-" + "\n";
                    continue;
                }

                stack2.push(stack1.pop());
                output += "+" + "\n";

                if (stack2.peek().equals(queue.peek())) {
                    queue.poll();
                    stack2.pop();
                    output += "-" + "\n";
                }
            } else if (stack1.empty()) {
                if (stack2.peek().equals(queue.peek())) {
                    queue.poll();
                    stack2.pop();
                    output += "-" + "\n";
                } else {
                    output = "NO";
                    break;
                }
            }
        }

        System.out.println(output);
    }
}

 

---

시도 2

: 되긴하는데 이번엔 출력초과 ㅋㅋㅋㅋ (인텔리상에선 심지어 잘 됨)

public class no1874 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine());
        Stack<Integer> stack = new Stack<>();

        int count = 0;
        String str = "";
        for(int i=1 ; i<=T ; i++) {
            int A = Integer.parseInt(br.readLine());

            if(stack.empty()) {
                count++;
                stack.push(count);
                bw.write("+" +"\n");
            }

            while(A!=stack.peek()) {
                if(count==T && A!=stack.peek()) {
                    str = "NO";
                    break;
                }

                count++;
                stack.push(count);
                bw.write("+" +"\n");
            }
            if(str.equals("NO")) {
                System.out.println("\n" +str);
                break;
            }

            stack.pop();
            bw.write("-" +"\n");
        }

        if(!str.equals("NO")) {
            bw.close();
        }
    }
}

---

시도 3 (성공)

: 결론은 출력 도구 문제였음

: StringBuilder를 사용해야함

1. 메모리 초과 원인 = 쌩으로 String에 넣어서 발생

2. 출력 초과 원인 = No 출력시, BufferWriter에 넣어둔 것을 없애지 않아서 발생

import java.io.*;
import java.util.Stack;

public class no1874 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        Stack<Integer> stack = new Stack<>();
        boolean no = false;
        int count = 0;
        for(int i = 0; i < T; i++) {
            int num = Integer.parseInt(br.readLine());

            if(stack.empty()) {
                count++;
                stack.push(count);
                sb.append("+").append("\n");
            }

            while(stack.peek()!=num && count<=T) {
                count++;
                stack.push(count);
                sb.append("+").append("\n");
            }

            if(stack.peek()!=num && count>T) {
                no = true;
                break;
            }

            stack.pop();
            sb.append("-").append("\n");
        }

        if(no) {
            System.out.println("NO");
        } else {
            System.out.println(sb);
        }
    }
}

---

추가 : Stack은 몇가지 단점이 있으므로, Deque가 더 좋다. 
참고 링크 : https://tecoble.techcourse.co.kr/post/2021-05-10-stack-vs-deque/

(이후 다른 글로 재정리 예정)