[백준] 1874. 스택 수열 (JAVA)

이번에 풀어 볼 문제는 <백준 1874번.  스택 수열>이다.

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

📌 문제 탐색하기

목표

스택 연산으로 주어진 수열을 만들 수 있는지 판단하기

해야 할 것

1. 스택에 어떤 규칙으로 담아야 주어진 수열을 만들 수 있는 지 판단할 수 있을까?

입력

[첫줄] 주어질 수의 개수 n (1 ≤ n ≤ 100,000)

[둘째줄 ~ ] 각 줄에 정수가 1개씩 주어짐 ( 1 ≤ 정수 ≤ n )

아이디어

1. 스택에 어떤 규칙으로 담아야 주어진 수열을 만들 수 있는 지 판단할 수 있을까?

 

현재 숫자를 표현할 cur 변수와 수열의 숫자를 표현할 target 변수를 선언

1) 스택에 push 를 해야하는 경우

: cur <= target 

2) 스택에서 pop 해야하는 경우

: 스택의 최상단 숫자 == target

3) 목표한 숫자를 만들 수 없는경우

: push를 할 수 있는 상황도 아니고, pop 해도 target과 스택 최상단 숫자가 다를 때

 

📌 코드 설계하기

1. ArrayDeque로 스택을 구현한다.

2. 위에 작성한 규칙에 따라 스택 연산을 시행한다.

 

📌 정답 코드

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

public class Main {
    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());
        ArrayDeque<Integer> stack = new ArrayDeque<>();

        int current = 1; // 스택에 푸시할 숫자
        boolean isPossible = true;

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

            // 스택에 푸시해야 하는 경우 : 현재 숫자가 목표 숫자보다 작거나 같을 때
            while(current<=target){
                stack.push(current++);
                sb.append("+\n");
            }

            // 스택의 최상단이 목표 숫자인 경우 pop
            if(stack.peek() != null & stack.peek() == target){
                stack.pop();
                sb.append("-\n");
            }else{
                // 목표 숫자를 만들 수 없는 경우 (push도 못하고 pop을 해야하는 데 target과 스택 제일 위 숫자가 다를 때)
                isPossible = false;
                break;
            }
        }

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

    }
}

 

📌 알게 된 것

if(stack.peek() == target){};

위와 같이 '==' 연산자를 사용한 경우는 stack.peek() 의 결과가 null이라도  NullPointerException이 발생하지 않는다.

하지만, '>','<' 와 같이 산술비교 연산자를 사용하는 경우에는 stack.peek()가 null이 되면 NullPointerException이 발생한다.

 

그러므로 아래와 같이 null 일 경우를 꼭 주의해서 처리해줘야 한다.

if(stack.peek()!= null && stack.peek() > target){};

 

 

Integer 와 int 의 값을 "==" 연산자로 비교할 수 있는가? ➡️ 가능하다. 이 경우, Integer 객체가 언박싱되어 int로 처리된다.

 

Integer == int : Integer 객체가 언박싱되어 int와 값 비교

Integer == Integer : 두 객체의 참조를 비교, 값이 같아도 객체가 다르면 false, 단 -128~127 범위 내에서는 캐싱된 동일 객체 참조

public class Main{
    public static void main(String[] args){
        Integer a = Integer.valueOf(1);
        Integer b = Integer.valueOf(1);

        System.out.println(a==b); //true

        Integer c = Integer.valueOf(129);
        Integer d = Integer.valueOf(129);

        System.out.println(c==d); //false
    }
}

 

Integer.equals(Integer) : 두 Integer 객체의 값을 비교, 값이 같으면 true