[ Algorithm ] 백준 1874번 : 스택 수열 - [JAVA]

Minsu Lee·2023년 3월 2일

Java algorithm

baekjoon

목록 보기

15/16

🎆1874번 스택 수열🎆

📌문제

🔍문제 설명

문제 링크 : https://www.acmicpc.net/problem/1874

🔍예제 입력

8
4
3
6
8
7
5
2
1

🔍예제 출력

+
+
+
+
-
-
+
+
-
+
+
-
-
-
-
-

📌풀이

🔍풀이 설명

자료 구조 (Date-Structure)를 이용하여 푸는 문제였다. Stack사용

Stack : 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료 구조
스택(Stack)는 LIFO(Last In First Out) 를 따른다. 즉, 가장 최근에 스택에 추가한 항목이 가장 먼저 제거될 항목이다.

pop(): 스택에서 가장 위에 있는 항목을 제거한다.

push(item): item 하나를 스택의 가장 윗 부분에 추가한다.

peek(): 스택의 가장 위에 있는 항목을 반환한다.

isEmpty(): 스택이 비어 있을 때에 true를 반환한다.

이 문제에서는 스택 2개를 이용해 풀이했다. 스택의 특성인 LIFO때문이다. 우선 수열을 스택1(코드에선 array로 선언함)에 빼내야 하는 수를 순서로 넣어두고 비어있는 스택2에 1부터 n까지 push하면서 스택1와 비교하여 peek의 수가 같으면 둘 스택에 pop를 실행한다. 반복문 종료 후 stack이 비어있나 검사를 통해 수열이 만들어졌나 검사한다.

🔍코드

package Data_Structure;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;

//스택 수열
public class p1874 {
    public static void main(String[] args)throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        Stack<Integer> stack = new Stack<>();
        Stack<Integer> array = new Stack<>();

        for (int i=0; i<n ;i++) {
            int number = Integer.parseInt(br.readLine());
            stack.push(number);
        }
        //LIFO 성질이 있어서 다시 정렬 && stack는 비어있는 스택으로
        for (int i = 1; i < n+1; i++) {
            array.push(stack.pop());
        }

        for (int i = 1; i < n+1; i++) {
            if(i <= array.peek()){ //같거나 작으면 stack에 넣기
                stack.push(i);
                sb.append("+\n");
            }
            while (stack.size()>0 && stack.peek().equals(array.peek())){
                //stack의 사이즈가 0보다 크고 빼야하는 수가 나오면 stack에서 제거
                sb.append("-\n");
                stack.pop();
                array.pop();
            }
        }
        if(stack.isEmpty()){
            System.out.print(sb);
        }
        else{
            System.out.print("NO");
        }
    }
}