[백준] 스택 수열(JAVA)

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

설명

https://commit.tistory.com/14

[자료구조] 스택과 큐

후입선출 개념의 자료구조 스택을 제대로 이해하고 있는지 알아보는 문제다

스택에 대해서 본인은 작년에 포스팅도 쓴 적이 있다

 

처음에는 문제가 이해가 안됐다

문제가 개떡같이 적힌거지 내 문해력에 문제가 없길 바란다

 

정수 입력을 배열에 먼저 받아두고

스택에는 1부터 n까지 입력하면서

배열의 정수와 일치한다면 스택에서 빼 주었다

동시에 +, - 출력도 함께 해주었다

풀이

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

/*
백준 1874 스택 수열
스택은 LIFO(후입선출) 개념의 자료구조
스택에 넣는 값은 오름차순 정렬
 */
public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        int n = Integer.valueOf(br.readLine());

        Stack<Integer> stack = new Stack<>();
        int[] arr = new int[n + 1];
        // 입력을 배열에 넣어줌
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.valueOf(br.readLine());
        }

        // 스택에 차례대로 1부터 넣어주면서 동시에 스택과 비교
        int turn = 0;
        for (int i = 1; i < n + 1; i++) {
            // 스택에 추가할 때마다 + 출력
            stack.push(i);
            bw.write("+\n");

            // 넣자마자 배열과 비교했을 때 같은 정수라면 빼줌
            while (!stack.isEmpty() && arr[turn] == stack.peek()) {
                stack.pop();
                bw.write("-\n");

                // 배열의 다음 정수로
                turn++;
            }
        }

        bw.flush();
        bw.close();
    }
}

처음에는 "NO" 출력을 까먹고 풀었다

개억까당하는 줄 알았다

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/*
백준 1874 스택 수열
스택은 LIFO(후입선출) 개념의 자료구조
스택에 넣는 값은 오름차순 정렬
안되는 거면 NO 출력
NO를 위해 큐에다가 출력을 저장해두고 마지막에 출력
 */
public class cote {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        int n = Integer.valueOf(br.readLine());

        Stack<Integer> stack = new Stack<>();
        // 답안지
        Queue<Character> queue = new LinkedList<>();
        int[] arr = new int[n + 1];
        // 입력을 배열에 넣어줌
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.valueOf(br.readLine());
        }

        // 스택에 차례대로 1부터 넣어주면서 동시에 스택과 비교
        int turn = 0;
        for (int i = 1; i < n + 1; i++) {
            // 스택에 추가할 때마다 큐에 + 추가
            stack.push(i);
            queue.offer('+');

            // 넣자마자 배열과 비교했을 때 같은 정수라면 빼줌
            // 뺄 때마다 - 추가
            while (!stack.isEmpty() && arr[turn] == stack.peek()) {
                stack.pop();
                queue.offer('-');

                // 배열의 다음 정수로
                turn++;
            }
        }

        // NO 구분
        if (!stack.isEmpty()) {
            bw.write("NO");
        } else {
            while (!queue.isEmpty()) {
                bw.write(queue.poll() + "\n");
            }
        }

        bw.flush();
        bw.close();
    }
}

스택(1부터 n까지 저장), 배열(입력 정수 저장), 큐(출력 정수 저장) 모두 사용한다

앞서 설명한대로 먼저 배열에 정수를 입력받았다

다음은 스택에 1부터 n까지 입력하면서 +를 큐에 입력해주었다

만약 스택에 넣은 정수가 배열의 정수와 일치한다면 스택에서 빼주고 동시에 -를 큐에 입력해주었다

 

마지막엔 큐에 저장된 +, -를 출력해주었다

그러나 스택에 아직 뭐가 남아있다면 NO를 출력해주었다

이 NO를 출력하기 위해 큐를 사용했다

 

문제를 이해하기만 한다면 금방 해결할 수 있는 문제다

https://github.com/qTeTp/Algo/tree/74dbb9ee5d91ad6bb7ac72fdc3688ffd0a47167a/%EB%B0%B1%EC%A4%80/Silver/1874.%E2%80%85%EC%8A%A4%ED%83%9D%E2%80%85%EC%88%98%EC%97%B4

Algo/백준/Silver/1874. 스택 수열 at 74dbb9ee5d91ad6bb7ac72fdc3688ffd0a47167a · qTeTp/Algo