스파르타 알고리즘 트랙 문제 4일차 - 1 #1874 스택 수열

문제

스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

 

해결 과정

수열과 Stack의 관계를 비교할 수 있다면, 쉽게 문제를 해결할 수 있다.

먼저, Stack에서 가장 위에 있는 수를 a, 비교하고자 하는 수열의 요소를 b라고 했을 때, Stack의 모든 요소들은 a보다 작거나 같다. Stack에는 1부터 a까지의 수를 순차적으로 쌓았기 때문에, a보다 b가 작을 경우 해당 요소를 만족시킬 수 없기 때문에 주어진 수열은 만들 수 없다. a보다 b가 크다면, a+1을 Stack에 저장하고, 이를 a가 b와 같아질 때까지 반복한 다음 Stack에서 수를 꺼낸다.

 

위의 과정을 반복해서 만족시킬 수 없는 경우가 없다면 만들 수 있는 것으로 판단하고, 결과값을 출력한다.

import java.io.*; import java.util.LinkedList; import java.util.*; import static java.lang.Integer.parseInt; public class Main {     public static void main(String[] args) throws IOException {         BufferedReader a = new BufferedReader(new InputStreamReader(System.in));         BufferedWriter b = new BufferedWriter(new OutputStreamWriter(System.out));         int N = parseInt(a.readLine());         int nextnum=1;         Stack<Integer> arr = new Stack<>();         Queue<String> ans = new LinkedList<>();         while (N!=0){             int order = parseInt(a.readLine());             while(order>=nextnum){                 ans.add("+\n");                 arr.push(nextnum);                 nextnum++;             }             int tmp = arr.pop();             if (tmp>order) {                 ans.clear();                 ans.add("NO\n");                 break;             }             ans.add("-\n");             N--;         }         while(ans.size()!=0)             b.write(ans.poll());         b.flush();         b.close();     } }

수열의 모든 요소들을 전부 확인해 봐야 만들 수 있는지 없는지 알 수 있기 때문에 Stack에 쌓고 빼는 과정은 별도의 리스트에 저장해 두어야 한다. 선입선출이 가능한 Queue 자료구조를 활용해 저장해 두었다. 또한 주어진 수열을 만들 수 없다는 판단이 내려질 경우 지금까지 저장한 정보를 모두 지운 후 NO를 출력할 수 있도록 구성하였다.

 

지금까지 해왔던 Stack의 사용과 동일하기에 큰 어려움 없이 문제를 풀 수 있었다.