[백준] 1874번 스택 수열 - Java, 자바

난이도

실버 3

유형

스택

문제

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

풀이

문제 접근
1부터 n까지 수를 스택에 넣었다가 뽑아 늘어놓음으로써 하나의 수열을 만들 수 있다.
-> 1부터 n까지 차례로 스택에 push하고 적절히 pop하며 주어진 수열을 만들어라.

문제 풀이
1. 1부터 n까지는 무조건 push해야한다.
2. 특별한 경우에 pop하며 주어진 수열을 만들어야하는데 특별한 경우란 스택의 top의 값과 주어진 수열의 맨 앞 원소와 같은 경우이다.
(주어진 수열은 큐를 이용.)
-> while문을 사용해서 특별한 경우일 때 계속 pop하도록 실행한다.

따라서 코드를 아래와 같이 구현했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

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

        int n = Integer.parseInt(br.readLine());
        Queue<Integer> q = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            q.add(Integer.parseInt(br.readLine()));
        }

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


        for (int i = 1; i <= n; i++) {
            s.push(i);
            sb.append("+").append("\n");

            if (!q.isEmpty() && !s.isEmpty() && s.peek() == q.peek()) {
                while (!q.isEmpty() && !s.isEmpty() && s.peek() == q.peek()) {
                    s.pop();
                    int b = sb.append("-").append("\n");
                }
            }

        }
        if (s.isEmpty()) {
            System.out.println(sb);
        } else {
            System.out.println("NO");
        }


    }


}

구현해보고 나니 틀렸습니다가 떴다.
코드의 로직은 맞는 것 같은데 사소한 부분에서 틀렸을 것 같아서 계속 고민했다.

알아낸 점
1. 굳이 while문과 같은 if문을 쓸 필요가 없다.

if (!q.isEmpty() && !s.isEmpty() && s.peek() == q.peek()) {-> 제거 

2. s.peek() == q.peek() <- 옳지 않은 비교
   int 는 == 으로 비교할 수 있지만
   Integer는 equals()로 비교해야한다.

위 두가지를 수정해서 제출했더니 맞았다.

코드

package 스택;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

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

        int n = Integer.parseInt(br.readLine());
        Queue<Integer> q = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            q.add(Integer.parseInt(br.readLine()));
        }

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


        for (int i = 1; i <= n; i++) {

            s.push(i);
            sb.append("+").append("\n");

            while (!q.isEmpty() && !s.isEmpty() && s.peek().equals(q.peek())) {
                s.pop();
                q.poll();
                sb.append("-").append("\n");
            }


        }
        if (s.isEmpty()) {
            System.out.println(sb);
        } else {
            System.out.println("NO");
        }

    }


}