백준 1874 스택 수열 - Java 자바 문제 풀이

문제 해설

1부터 n까지의 수를 차례로 스택에 넣었다가 뺌으로써 문제에서 주는 임의의 수열을 만들 수 있다면, 스택에 숫자를 넣고 빼는 순서를, 아니라면 NO를 출력하는 문제입니다.

수를 오름차순으로 차례로 넣고 있기 때문에 스택의 가장 윗부분 숫자 보다 크거나 같은 숫자는 뺄 수 있지만, 작은 숫자는 빼낼 수 없습니다. 따라서 NO를 출력해야 합니다.

 

문제 풀이 계획

필요 변수

변수명	타입	초기값	설명
n	int		첫째 줄에 주어지는 정수
num	int		n번에 걸쳐 입력 받을 숫자(수열의 숫자)
cur	int	1	1부터 스택에 들어갈 오름차순 숫자
arr	int[]		부른 숫자를 저장할 배열
pos	int	0	배열(스택)의 마지막 인덱스를 가리키는 변수

 

해결 로직

1. n을 입력 받는다.
2. 수열의 숫자 num을 입력 받는다.
3. 입력 받은 숫자 num과 오름차순 숫자 cur이 같아질 때까지 스택에 삽입한다.
4. num과 스택의 top이 같으면 pop을 하고, num이 스택의 top보다 작다면 즉시 NO를 출력한다.
5. 정상처리 결과를 출력한다.

 

풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	
	public static int n;
	public static int cur = 1; // 스택에 1부터 오름차순으로 들어갈 숫자
	public static int[] arr;
	public static int pos = 0; // pos는 항상 다음 값이 삽입될 위치를 가리킨다.
	public static boolean isPossible=true;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		
		// 1. n을 입력 받는다.
		n = Integer.parseInt(st.nextToken());
		arr = new int[n];
		
		// 2. 분기처리한다.
		while(n-- > 0) {
			
			st = new StringTokenizer(br.readLine());
			int num = Integer.parseInt(st.nextToken()); // 입력 받은 숫자
			
			while(cur <= num) { // 입력 받은 숫자와 오름차순으로 넣는 숫자가 같아질 때까지 스택에 삽입한다.
				arr[pos++] = cur++;
				sb.append('+').append('\n');
			}
			
			int top = (pos==0) ? 0 : arr[pos-1]; // 스택 마지막 원소
			
			if(num == top) { // 입력 받은 숫자와 스택의 top이 같으면 pop하고
				pos--;
				sb.append('-').append('\n');
			} else { // 입력 받은 숫자가 스택의 top보다 작으면 NO를 출력한다.
				isPossible=false;
			}
		}
		
		// 3. 결과를 출력한다.
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		if(isPossible) {
			bw.write(sb.toString());
		} else {
			bw.write("NO");
		}
		
		bw.flush();
		bw.close();
	}	
}

 

1874번: 스택 수열