[BOJ] 1874번: 스택수열 (Java)
문제
코드(JAVA)
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();
Stack<Integer> stack = new Stack<>();
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
for(int i =0 ;i < n ; i++) arr[i] = Integer.parseInt(br.readLine());
int cnt = 1;
int i;
for(i =0 ; i < n ; i++) {
if(stack.isEmpty()) {
if(cnt>arr[i]) break;
stack.push(cnt++);
sb.append("+\n");
}
if(arr[i] > stack.peek()) {
if(cnt > arr[i]) break;
while(stack.peek() != arr[i]) {
stack.push(cnt++);
sb.append("+\n");
}
}
else if(arr[i] < stack.peek()) {
while(stack.peek() != arr[i]) {
stack.pop();
sb.append("-\n");
}
}
if(arr[i] == stack.peek()) {
stack.pop();
sb.append("-\n");
}
}
if(i != n || !stack.isEmpty()) System.out.println("NO");
else System.out.print(sb.toString());
}
}
설명
입력: BufferedReader
출력: StringBuilder
기본적으로,
현재 비교하고 있는 배열 값(arr[i])과 현재 stack에 맨 위에 값을 비교.
If(arr[i] > stack.peek())이라면,
아직 스택에 해당 값(arr[i])가 안들어가 있는 경우이므로 stack.peek() == arr[i]까지 스택에 cnt를 push
If(arr[i] < stack.peek())이라면,
스택안에 해당 값이 들어있는 경우이므로, stack.pop값이 arr[i]일때까지 pop
💡 이때, 주의 할 점.
push할 때, 현재 스택에 들어갈 값(cnt)보다 비교 할 값(arr[i])가 더 크다면
스택에는 계속 arr[i]보다 큰값만 쌓이게 되고, 결국 무한루프를 돌게 됨.
이 부분에 대한 분기문을 잘 활용해야 메모리초과, 시간초과가 나지 않음 (ノへ ̄、)
반례(내 코드 기준!)
1
1
+
-
3
1
2
3
+
-
+
-
+
-
4
4
2
3
1
NO
Author And Source
이 문제에 관하여([BOJ] 1874번: 스택수열 (Java)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dot2__/BOJ-1874번-스택수열-Java저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)