🎇 문제

1874번 : 스택 수열

🎇 문제 설명

스택에 1부터 N까지의 수를 스택에 넣고(push) 빼는(pop) 과정을 통해 임의의 수열과 일치하는 수열인지 판단하는 문제이다.

🎇 접근 방법

입력값 상단의 N을 제외한 값들을 받을 때, 값(value)을 출력하기 위해서는 1부터 값까지 Stack에 넣어준 뒤 value를 pop() 해주는 방식으로 구현하면된다.

Stack에 넣어줄 때에는 push() 해당 값을 뺄 때는 pop() 메서드를 사용하여 빼주면 된다.

해당 문제에서 주의해야할 점은 2가지 이다.
1. start 변수의 역할

• 1 ~ value의 값을 Stack에 담을 때 Stack에 이미 해당 숫자가 담겨있는 경우, 중복을 피해야 하기 때문에 마지막에 value로 선정된 값에 +1된 값부터 stack에 넣어줘야 한다. 이를 위해서는 start라는 변수를 선언하여 이전에 value 값을 담고 있어야 하며, start 변수가 value 변수보다 작아야만 Stack에 추가하는 동작이 수행되도록 구현해야 한다.

2. NO를 출력하는 경우

• Stack에 값이 저장되는 순서는 오름차순으로 저장되기 때문에, pop() 시에도 이를 고려한 value가 입력값으로 들어와야 한다. 하지만, 입력값과 stack의 상위 요소가 같지 않은 경우, 오름차순을 고려하지 않은 요구사항이라 보고 NO를 출력하는 동작이 수행되도록 구현해야 한다.

return

• 자바에서 void 메서드 안에 return 예약어 사용 시, 메서드 종료를 의미한다.
• 반복문 내에서 break 예약어 사용 시에는 반복문 종료, continue 예약어 사용 시에는 조건에 해당하는 행동을 건너뛰도록 해주는 역할을 한다.

🎇 제출 코드

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

public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        Stack<Integer> stack = new Stack<>();
        int start = 0;
        
        while(N-- > 0){
            int value = Integer.parseInt(br.readLine());
            
            if(value > start){
                for(int i = start+1; i <= value; i++ ){
                    stack.push(i);
                    sb.append("+").append("\n");
                }
                start = value;
            }else if(stack.peek() != value){
                System.out.print("NO");
                return;
            }
            
            stack.pop();
            sb.append("-").append("\n");
        }
        
        System.out.println(sb);
        br.close();
    }
}

🎇 다른 방식

Stack 클래스를 사용하는 대신에 배열을 사용하여 구현한 코드

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

public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        int[] stack = new int[N];
        int idx = 0;
        int start = 0;
        
        while(N-- > 0){
            int value = Integer.parseInt(br.readLine());
            
            if(value > start){
                for(int i = start+1; i <= value; i++ ){
                    stack[idx] = i;
                    idx++;
                    sb.append("+").append("\n");
                }
                start = value;
            }else if(stack[idx-1] != value){
                System.out.print("NO");
                return;
            }
            
            idx--;
            sb.append("-").append("\n");
        }
        
        System.out.println(sb);
        br.close();
    }
}

참조 포스팅

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