[BOJ] 1874 - 스택 수열 (Java)

알고리즘

• 자료 구조
• 스택

1. 문제

• 스택을 활용하여 주어진 수열을 만들 수 있는지를 판단하는 문제
  

2. Idea

• 아이디어 내용

3. 풀이

3.1. 변수 입력

• Stack stack: 수열을 만들기 위한 스택
• N: 수열의 길이
• start: 수열의 시작값

Scanner in = new Scanner(System.in);
StringBuilder sb = new StringBuilder();	// 출력할 결과물 저장
		
Stack<Integer> stack = new Stack<>();
		
int N = in.nextInt();
int start = 0;

3.2. 반복문(N번) 수행 및 스택 수열 처리

• 입력으로 받은 수열의 값을 value 변수에 저장
  if value가 start보다 크다면, 현재 스택의 상태에 따라 수열을 생성
• start + 1부터 value까지의 수를 스택에 push하고, 각각의 push 연산을 sb에 저장
  -> 현재 스택의 상태를 표현
• start 값을 value로 업데이트 + 다음 수열을 만들 때 오름차순을 유지
  • if 스택의 맨 위의 값이 value와 같지 않다면, 입력받은 수열을 만들 수 없는 경우이므로 "NO"를 출력하고 프로그램을 종료
  • else 스택에서 pop 연산을 수행하고 sb에 "-"를 추가하여 수열의 결과를 표시

		// N 번 반복
		while(N -- > 0) {
			
			int value = in.nextInt();
			
			if(value > start) {
				// start + 1부터 입력받은 value 까지 push
				for(int i = start + 1; i <= value; i++) {
					stack.push(i);
					sb.append('+').append('\n');	// + 를 저장한다. 
				}
				start = value; 	// 다음 push 할 때의 오름차순을 유지하기 위한 변수 초기화 
			}
			
			// top에 있는 원소가 입력받은 값과 같이 않은 경우  
			else if(stack.peek() != value) {
				System.out.println("NO");
				return;		// 또는 System.exit(0); 으로 대체해도 됨. 
			}
			
			stack.pop();
			sb.append('-').append('\n');
			
		}

3.3. 결과 출력

System.out.println(sb);

4. 전체코드

import java.util.Scanner;
import java.util.Stack;
 
public class Main {
	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();	// 출력할 결과물 저장
		
		Stack<Integer> stack = new Stack<>();
		
		int N = in.nextInt();
		
		int start = 0;
		
		// N 번 반복
		while(N -- > 0) {
			
			int value = in.nextInt();
			
			if(value > start) {
				// start + 1부터 입력받은 value 까지 push
				for(int i = start + 1; i <= value; i++) {
					stack.push(i);
					sb.append('+').append('\n');	// + 를 저장한다. 
				}
				start = value; 	// 다음 push 할 때의 오름차순을 유지하기 위한 변수 초기화 
			}
			
			// top에 있는 원소가 입력받은 값과 같이 않은 경우  
			else if(stack.peek() != value) {
				System.out.println("NO");
				return;		// 또는 System.exit(0); 으로 대체해도 됨. 
			}
			
			stack.pop();
			sb.append('-').append('\n');
			
		}
		
		System.out.println(sb);
	}
}