[백준] 1874 스택 수열 - Java

 

 

 

다 풀고 나서 사소한 실수 때문에 1시간동안 삽질을 한 문제이다.

 

문제 이해가 정말정말 중요하다.

예시와 내가 푼 방법으로 간단하게 설명해 보면,

8 4 3 6 8 7 5 2 1 예시로 왼쪽과 같이 입력받았다고 하자.

처음 입력값은 4 이다.

stack에 4번 push를 진행한다. => stack = {1,2,3,4} 출력 결과 = {}

입력값이 4 이므로 pop을 수행한다. => stack = {1,2,3} 출력 결과 = {4}

다음 입력값은 3 이다.

이미 스택에 1.2.3.이 있기 때문에 pop으로 꺼내준다. => stack = {1,2} 출력 결과 = {4,3}

다음 입력값은 6 이다.

스택에 6은 없다. push를 진행하자. 이 때. push하는 수는 이전의 입력값 중 가장 큰 수 +1 이다.

 stack = {1,2,5,6} 출력 결과 = {4,3}

pop으로 꺼내주자. => stack = {1,2,5} 출력 결과 = {4,3,6}

 

위를 반복한다...

 

여기서 NO를 출력하게 되는 경우도 고려해야 한다.

pop을 진행하기 전에 스택의 가장 위에 있는 원소와 현재의 입력값이 같다면 pop을 진행할 수 있고, 같지 않다면 NO를 출력해야 한다.

 

코드를 통해 알아보자.

 

import java.util.*;

public class Main {
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();

		int cycle = sc.nextInt();
		Stack<Integer> st = new Stack();
		boolean checking = false;
		int[] arr = new int[cycle];

		for (int i = 0; i < cycle; i++) {
			arr[i] = sc.nextInt();
		}

		int check = 0;

		for (int i = 0; i < cycle; i++) {
			if (arr[i] > check) {
				for (int j = check + 1; j < arr[i] + 1; j++) {
					st.push(j);
					sb.append("+");
					sb.append("\n");
				}
				check = arr[i]; // ++++ 스택에 1234 체크는 4 입력값 4 // ++++--++ 스택에 1256 체크는 6 입력값 6
			} // NO를 입력하는 경우를 구현해야 함 // ++++--++-++ 스택에 12578 체크는 8 입력값 8

			if ((st.peek() == arr[i]) == false) { // 포함함 패스. // 포함함 패스.
				System.out.print("NO");
				checking = true;
				break;

			}

			st.pop(); // ++++- 스택에 123 다음 입력값 3 // ++++-- 스택에 12 다음 입력값 6 체크 4 // ++++--++- 스택에 125
						// 체크는 6 다음 입력값 8
			sb.append("-"); // ++++--++-++- 스택에 1257
			sb.append("\n");
		}
		if (checking) {

		} else {
			System.out.print(sb);
		}
		
		
	}
}

 

코드를 작성할 때는 항상 꼼꼼해지자.

사소한 실수는 찾기 힘들지만 치명적이다.