[JAVA][Baekjoon] 1874번 스택 수열

 

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

 

728x90

📌 접근 방법 

• 기준이 되는 자연수를 추가하여 해당 수와 비교하며 진행하였다. (k = 1)
• 현재 수열 값 >= k
  • 해당 수열 값이 될 때까지 push(+) 해준 후 도달하면 해당 값을 Pop(-) 해준다.
• 현재 수열 값 < k
  • 자연수보다 작은 값을 찾으려면 이미 스택에 넣어둔 값이므로 pop을 통해 스택에 있는 값을 꺼낸다. 
  • 꺼낸 값이 현재 수열 값이 아니라면 더이상 후입선출 원리로 계산할 수 없으므로 NO를 출력한 뒤 종료한다.
  • 꺼낸 값이 현재 수열 값과 같다면 pop을 했으므로 - 를 추가한 후 다시 실행한다.

 

✅ pass code

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

public class Main {
    public static Scanner sc = new Scanner(System.in);
    public static void main (String [] args) throws IOException {
        int N = sc.nextInt();

        int [] arr = new int[N];
        for(int i = 0; i < N; i++){
            arr[i] = sc.nextInt();
        }

        StringBuffer str = new StringBuffer();

        int k = 1;
        boolean result = true;

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

        for(int i = 0; i < N; i++) {
            int num = arr[i];
            if(k <= num){
                while(k <= num){
                    stack.push(k++);
                    str.append("+\n");
                }
                stack.pop();
                str.append("-\n");
            }
            else{
                int n = stack.pop();
                if(n > num) {
                    System.out.println("NO");
                    result = false;
                    break;
                }
                else {
                    str.append("-\n");
                }
            }
        }
        if(result == true){
            System.out.println(str.toString());
        }
    }
}

 

처음에 String str = ""; 이렇게 해서 기호를 추가했더니 메모리 초과 오류가 났다

➡️ StringBuffer를 이용해주니 에러가 해결되었다!