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

 

---

문제

• 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써 하나의 수열을 만들 때, n개의 수로 이루어진 수열을 만드는데 필요한 연산을 출력하는 문제.

 

아이디어

• 문제 그대로의 내용을 구현한다.
• 수열을 만들기 위해서는 n번의 pop 연산이 있어야 한다.
• 이를 이용해 스택을 구현하고, 스택에 찾고자 하는 수가 있는지 없는지 여부에 따라 push, pop을 수행한다.
  • 스택이 비었을 경우 무조건 새로운 수를 입력하고, 비어있지 않을 경우 가장 위에 있는 수가 찾고자 하는 수 인지 판별한다.
  • 찾고자 하는 수라면 pop 연산을 한 후, pop 연산 횟수 + 1
  • 찾고자 하는 수가 아니라면, 숫자 num을 스택에 push 한 후, num++
  • push 후에는 num이 n을 넘겼는지 안넘겼는지 판단
  • 넘겼다면 n개의 수로 만들 수 없는 수열이므로 반복문 종료
• 반복문을 탈출해 n번의 pop 연산이 수행되었다면 정상 종료(수열 생성), 다르다면 비정상 종료(수열 생성 실패)로 간주한다.

 

풀이

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

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

        int n = Integer.parseInt(br.readLine());

        int[] numArr = new int[n];

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

        Deque<Integer> stack = new ArrayDeque<>();
        
        // pop 연산의 횟수를 셀 cnt 선언
        int cnt = 0;
        
        // 스택에 저장될 수를 카운트
        int num = 1;
        
        // n개의 수를 모두 나열해 수열을 만들 때까지 반복
        while(cnt != n) {
            // 스택이 비었으면 새로운 수 push
            if(stack.isEmpty()) {
                stack.addFirst(num);
                num++;
                
                // num이 n을 넘겼을 경우(구성할 수 없는 수열) 종료
                if(num > n+1) {
                    break;
                }
                sb.append('+').append('\n');
                continue;
            }
            
            // 스택의 첫 요소가 찾고자 하는 수가 아니라면 새로운 수 push
            if(stack.peekFirst() != numArr[cnt]) {
                stack.addFirst(num);
                num++;
                
                // num이 n을 넘겼을 경우(구성할 수 없는 수열) 종료
                if(num > n+1) {
                    break;
                }
                sb.append('+').append('\n');
            }
            // 스택의 첫 요소가 찾고자 하는 수라면 pop 후 cnt+1
            else {
                stack.removeFirst();
                cnt++;
                sb.append('-').append('\n');
            }
        }
        
        // while 문을 탈출했는데, pop 연산 수가 n과 일치하지 않는다면 수열 생성 실패
        if(cnt != n) {
            sb = new StringBuilder().append("NO").append('\n');
        }
        System.out.println(sb);
    }
}

 

 

채점 결과

1874번 채점 결과

 

문제 링크

• 1874번: 스택 수열 (acmicpc.net)