[JAVA] 백준-1874 스택 수열

문제

https://www.acmicpc.net/problem/1874

---

스택을 이용하여 문제를 풀 수 있다.

배열을 통해 스택을 구현하여 푸는 방법과 스택 클래스를 이용하는 방법을 제시하겠다.

만약 스택이 잘 이해되지 않는다면 이곳에 자세하게 설명되어 있으니 꼭 보고 오길 바랍니다.

 

기본적으로 풀 방법으로는 실제로 스택을 이용하여 직접 입력된 값이 가능한지 일일이 넣었다 빼는 방식이다.

 

값이 입력되면 스택에 입력된 숫자까지 순차적으로 저장한 뒤에

그 입력된 값을 뺀다.

그 후에 입력된 값이 스택의 끝부분과 맞지 않다면 뺄 수 없기 때문에 NO를 출력한다.

예제 2번을 예로 들어 보자면

• 1이 입력되었으니 1을 push한뒤에  1을 pop 한다..
• 2가 입력되었으니 2를 push한뒤에  2를 pop 한다.
• 5가 입력되었으니 3,4,5를 push한뒤에  5를 pop 한다.
• 3이 입력되었으나 끝에 있은 숫자는 4이기 때문에 pop이 불가능하다. 즉 NO를 출력

---

1. 배열로 스택 구현

배열은 한정된 공간이기 때문에

실제 값의 증가와 인덱스를 분리하여 저장한다.

예를 들어 배열에 1~4까지 값을 push 한다고 가정하자.

이후 4를 pop한뒤에 다시 push를 하려고 한다면 4가 저장된 위치부터 5를 저장하면 된다.

즉 값의 증가는 1, 2, 3 순으로 증가하지만 인덱스는 pop을 하면 감소했다가 다시 증가하기 때문에 따로 저장하는 것이다.

아래의 코드를 보고 이해해 보길 바란다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb= new StringBuilder();
		int n=Integer.parseInt(br.readLine());
		int[] arr=new int[n];
		int start=0; //실제로 저장되는 값 (ex. 1,2,3,...)
		int idx =0; //배열의 인덱스
		for(int i=0;i<n;i++) {
			int input=Integer.parseInt(br.readLine());
			if(input>start) { //만약 입력값이 지금까지 저장된 값보다 작다면
				for(int j=start+1;j<=input;j++) {
					arr[idx]=j; //배열에 값 저장
					idx++; //값이 저장된 인덱스 증가
					sb.append("+").append('\n');
				}
				start=input; //현재까지 입력된 값
			}else if(arr[idx-1]!=input) { //만약 입력된 값이 내림차순에 맞지않다면
				System.out.println("NO");
				return;
			}
			idx--; //pop()
			sb.append("-").append('\n');
		}
		System.out.println(sb);
	}
}

---

2. 스택 클래스로 구현

스택 클래스로 구현하면 따로 인덱스를 저장할 필요 없이 직접 넣었다 빼면 된다.

기본적인 것은 위와 같다.

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

 

 

 

만약 이해가 되지 않는 부분이 있다면 댓글로 질문 남겨주시면 됩니다