스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.
1부터 n
까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.
첫 줄에 n (1 ≤ n ≤ 100,000)
이 주어진다. 둘째 줄부터 n
개의 줄에는 수열을 이루는 1이상 n
이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.
입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.
8
4
3
6
8
7
5
2
1
+
+
+
+
-
-
+
+
-
+
+
-
-
-
-
-
5
1
2
5
3
4
NO
-문제를 만든 사람: author5
-문제의 오타를 찾은 사람: bgjuw12
-데이터를 추가한 사람: djm03178, makusta, scala0114
import java.util.Scanner;
import java.util.Stack;
public class Code1874 {
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
String out="";
boolean no=false;
Stack<Integer> nums=new Stack<>();
int first=sc.nextInt();
StringBuilder sb=new StringBuilder();
int start=1;
for(int i=0;i<first;i++){//ex)4
nums.push(start);
// out+="+"+"\n";
sb.append("+"+"\n");
start++;
}
nums.pop();
// out+="-"+"\n";
sb.append("-"+"\n");
for(int i=1;i<n;i++){
int num=sc.nextInt();
if(!nums.empty()){
if(nums.peek()>num){
// out="";
// out="NO";
// System.out.println(out);
no=true;
}
else if(nums.peek()==num){
// out+="-"+"\n";
sb.append("-"+"\n");
nums.pop();
}
else{
int temp=start;
for(int j=temp;j<=num;j++){
nums.push(j);
// out+="+"+"\n";
sb.append("+"+"\n");
start++;
}
// out+="-"+"\n";
sb.append("-"+"\n");
nums.pop();
}
}
else{
int temp=start;
for(int j=temp;j<=num;j++){
nums.push(j);
sb.append("+"+"\n");
// out+="+"+"\n";
start++;
}
sb.append("-"+"\n");
// out+="-"+"\n";
nums.pop();
}
}
if(no){
sb.setLength(0);
sb.append("NO"+"\n");
}
System.out.println(sb);
}
}
BufferedWriter
를 사용하니 buffer
에 다 차버리면 알아서 출력되어버리는 것을 알게되었다. 그러므로 StringBuilder
를 이용했다!
처음에 String
에만 저장해두고 출력하니 메모리 초과
가 떴기 때문에 주석으로 처리해뒀다.
첫 번째 숫자 값만큼 일단 스택에 저장해둔다.
그다음 수를 봤을 때 스택에 저장되어있는 수인데, 만약 top
이 아니면 꺼낼 수 없기 때문에 no
가 된다.
top
이면 바로 꺼내면 되고, 만약 저장되어 있지 않은 수라면 그만큼 또 스택에 저장하여 반복하면 된다.