[백준 JAVA] 1874 스택 수열

1874 스택 수열

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

문제설명

stack의 push와 pop을 사용한 데이터 삽입과 추출

접근방식

O(n) 선형 시간복잡도

 

스택에 숫자를 넣을 때 변수를 증가시키면서 스택에 최대 n개의 숫자를 넣을 수 있다.

입력의 크기인 수열의 길이 n에 비례하여 선형 시간에 수행된다.

문제 조건 분석 과정

 

1. 스택을 사용하여 수열을 만든다.

2. 입력된 숫자를 스택에 저장하고, 수열을 만들때 저장된 숫자를 빼낸다

3. 스택이 후입선출임에 유의하자

자료구조

Stack<Integer>

 

 정수형 데이터를 저장하는 스택을 생성.

 

• push: st.push(current)를 사용하여 스택의 맨 위에 정수 current를 추가.
• 이 때, current는 수열에 들어갈 숫자를 의미한다.
• pop: st.pop()을 호출하여 스택의 맨 위에 있는 값을 제거하고 반환한다.
• 이 코드에서는 수열 처리의 일치 여부를 확인한다.
• peek: st.peek()을 호출하여 스택의 맨 위에 있는 값을 조회한다. 
• 스택의 top 값과 수열의 처리해야 할 숫자를 비교하기 위해 사용됩니다.
• isEmpty: st.isEmpty()를 사용하여 스택이 비어있는지 여부를 확인한다.
• 스택이 비어있는 경우와 아닌 경우를 처리한다.

 

틀린이유

스택의 후입선출을 이용한 push 와 pop 문제

 

만약, 수열이 [4, 3, 6, 8, 7, 5, 2, 1] 이라고 주어졌을때

스택에 순서대로1, 2, 3, 4를 스택에 넣은 후

수열에 4를 처리해야 할 때 pop을 수행하여 4를 수열에 추가한다.

 

올바른 접근 방식 및 해결 방식

스택, 큐에 대해서 아직 개념이 덜 잡힌 것 같다.

좀 더 공부해야겠다.............

전체코드

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

public class Main_1874스택수열 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Stack<Integer> st = new Stack<>();
        StringBuilder result = new StringBuilder();

        //수열 지정
        int n = Integer.parseInt(br.readLine());
        int[] sequence = new int[n];

        for(int i = 0; i < n; i++){
            sequence[i] = Integer.parseInt(br.readLine());
        }

        int current = 1; //수열에 들어갈 숫자

        for (int num : sequence){
            while (current <= num){
                st.push(current); //숫자를 스택에 push한다
                result.append("+\n"); //push 연산
                current++; //current 값 증가
            }

            //스택의 top이 수열에서 처리하는 숫자와 같은지 확인
            if(st.peek() == num){
                st.pop(); //수열에서 처리해야 할 숫자와 top이 일치하면 pop
                result.append("-\n");
            } else {
                System.out.println("NO"); //일치하지 않을 경우
                return;
            }
        }
        
        //수열 출력
        System.out.println(result.toString());
        br.close();
    }
}