BOJ_1874 : 스택 수열

👉 문제링크

1874번: 스택 수열

---

---

🔸 문제 분석 🔸

• 스택의 pop, push 연산과 후입 선출 개념을 정확하게 알고 있는지 묻는 문제이다.
• 스택에 넣는 자연수 값은 오름 차순 정렬이다.
  • 현재 수열 값 >= 자연수
    • 자연수가 현재 수열 값과 같아질 때 까지 자연수를 1증가시키며 스택에 push한다.
    • 마지막은 출력하기 위해 1번 pop한다.
  • 현재 수열 값 < 자연수
    • pop해서 스택의 가장 위 값을 확인한다.
      • 꺼낸 값이 현재 수열 값이 아니라면, 후입선출 원리에 따라서 수열을 표기할 수 없다. NO출력.
      • 현재 수열 값이라면 그대로 조건문을 나온다.

🔸 코드 🔸

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer();

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

        Stack<Integer> stack = new Stack<>();
        int num = 1;
        boolean result = true;
        for (int i = 0; i < n; i++){
            int su = Integer.parseInt(br.readLine());
            if (su >= num){
                while (su >= num){
                    stack.push(num++);
                    sb.append("+\n");
                }
                stack.pop();
                sb.append("-\n");
            }
            else {
                int pop = stack.pop();

                if (pop > su) {
                    System.out.println("NO");
                    result = false;
                    break;
                }
                else {
                    sb.append("-\n");
                }
            }
        }
        if (result) System.out.println(sb.toString());
    }
}

🔸 코드 해석 🔸

• Stack 클래스를 이용해서 스택을 사용한다.
• 입력 받은 수열 값을 이용해 스택 표현이 되는지 계산한다.

---

🔸 end 🔸

• 이전에 python으로 풀었던 문제인데, 다시 java로 풀어보니 새로웠다.
• java의 자료구조 클래스를 사용하는게 익숙지 않은데 좋은 연습이 되었다.
• 한 번에 출력하기 위해 StringBuffer도 사용했는데, 이전에는 StringBuilder를 사용해서 그 차이점이 무엇인가 포스팅을 찾아보았다.
  • String과 StringBuffer/StringBuilder의 차이점은 메모리가 불변성인지 가변성인지이다.
    • String은 변하지 않는 문자열을 자주 사용하는 경우 사용한다.
  • StringBuffer/StringBuilder는 문자열이 길어지면, 그 만큼 메모리를 늘려서 사용할 수 있게 해준다.
  • StringBuffer/StringBuilder의 차이점은 동기화(Synchronization)이다.
    • StringBuilder는 동기화를 지원하지 않지만 속도는 StringBuffer보다 성능이 좋다.
      따라서 단일 스레드 환경에서 문자열의 수정이 빈번한 경우 사용한다.
    • StringBuffer는 동기화를 지원하여 멀티 스레드 환경에서도 안전하게 동작한다.
      따라서 멀티 스레드 환경에서 문자열의 수정이 빈번한 경우 사용한다.
  • 이 문제 풀이에서는 StringBuilder를 사용하는게 더 성능이 좋았을 것이다.