백준(JAVA) 풀이/자료 구조

백준(JAVA) 1874번 스택 수열 풀이

개발윗미 2022. 8. 21. 09:29

Java으로 구현한 1874번 스택 수열 문제 풀이입니다.

 

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

 

1874번: 스택 수열

1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.

www.acmicpc.net


import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int count = 0;
		List<Integer> stack = new ArrayList<>();
		List<Character> result = new ArrayList<>();
		boolean flag = true;
		
		for (int i=0; i<n; i++) {
			int data = sc.nextInt();
			while (count < data) {
				count ++;
				stack.add(count);
				result.add('+');
			}
			
			if (stack.get(stack.size()-1) == data) {
				stack.remove(stack.size()-1);
				result.add('-');
			} else {
				flag = false;
				break;
			}
		}
		
		if (flag == true) {
			for (int i=0; i<result.size(); i++) {
				System.out.println(result.get(i));
			}
		} else
			System.out.println("NO");
	}
}

 

1. n개의 수를 입력받는데, 현재의 count 값이 입력받은 값(data) 이상이 될 때까지 아래와 같은 작업의 while문을 수행한다.

  - count를 1 증가시킨다.

  - stack 리스트에 count 값을 추가하고, result에 '+' 를 추가한다.

 

2. 만약 stack리스트의 가장 마지막 요소와 data가 같을 경우 stack의 마지막 요소를 빼내고 result 리스트에 '-'를 추가한다.

 

3. 그렇지 않을 경우 flag를 false로 갱신하고 break 한다.

 

4. 최종적으로 flag값을 확인하여 그 값이 false라면 "NO"를 출력하고, true라면 한 줄에 한 개씩 result 리스트의 요소를 출력한다.