[백준 1874번] 스택 수열 (JAVA)

백준 1874번 문제  -  스택 수열

1874번: 스택 수열

---

문제 분석

 

• N값과 N개의 수 입력
• 무조건 스택에 1~n까지의 수가 순서대로 push
• 이때 입력된 N개의 수가 pop 된 순서라고 한다면, push(+)와 pop(-)은 어떻게 진행된 것인지 출력

 

---

해결 키 포인트

• Stack 개념 이해가 필요
• Stack Class가 자바에 존재
• 동일한 수는 존재하지 않음
• 만약 해당 연산이 불가능한 경우 NO 출력
  • 불가능 한 경우:  now (현재값) | stack(TOP)  [ n ][ n+1 ] | [ n-1 ] (이전 pop된 값) → now가 n-1보다 작을 경우 && nn이 now 보다 작을 경우 ex) 3 | 4 | 5 → 3 > 5 && 3 < 4 

 

---

스택(Stack) 설명

 

스택의 구조는 다음과 같다. 즉 스택의 특징은 "삽입과 삭제 연산 방식: LIFO(후입선출)" 이다

 

• LIFO: Last-in first-out

Do It! 알고리즘 코딩 테스트 기본

 

 스택은 깊이 우선 탐색(DFS), 백트래킹 종류의 코딩 테스트에 효과적 

 

스택  용어

 

위치

• top: 삽입과 삭제가 일어나는 위치

 

연산

• push: top 위치에 새로운 데이터를 삽입
• pop: top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산
• peek: top 위치에 현재 있는 데이터를 단순 확인

---

코드

package ch01;

import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;

public class Main {
	public static void main(String [] args){
		Scanner sc = new Scanner(System.in);
		
		// n개의 수
		int N = sc.nextInt();
		int num [] = new int [N];
		
		// 해당 배열 가능 여부
		boolean stackCheck = true;
		
		// stack
		Stack<Integer> stack = new Stack<Integer>();
		
		// stack 입출력 배열
		ArrayList<String> result = new ArrayList<String>();
		
		// 수열 입력
		for(int i=0;i<N;i++) 
			num[i] = sc.nextInt();
		
		// 현재 스택의 개수
		int stackSum = 0;
		
		for(int i=0;i<N;i++) {
			// 현재 값이 이전 pop된 값보다 클 경우 (data push)
			if(i==0 || num[i]>num[i-1]) {
				// 현재 값(num[i]) 만큼 스택에 +num (push) and -1 pop
				for(int s=stackSum+1;s<=num[i];s++) {
					stackSum++;
					stack.push(s);
					result.add("+\n");
				}
				stack.pop();
				result.add("-\n");
			}
			// 현재 값이 이전 pop된 값보다 작을 경우 (data pop)
			else {
				int pop = stack.pop();
				result.add("-\n");
				
				// 현재 top에 있는 수가 현재 값보다 클 경우
				if(pop > num[i]) {
					stackCheck = false;
					break;
				}
			}
		}
		if(stackCheck)	{
			for(int i=0;i<N*2;i++)
				System.out.print(result.get(i));
		}
		else
			System.out.print("NO");
	}
}

---

추가적인 스토리

 

stack class와 stack을 저장하는 배열을 만들지 않고, 해당 문제를 풀고자 하였으나 완성하지 못하였음.

• 백준 검사기 결과 : 출력 초과 발생
• 문제원인 (예상): TOP을 정확히 알기 어려워 해당 배열이 불가능 한 경우를 알아내는 코드가 허술 하였다

 

결론적으로 stack이나 array를 쓰지 않고는 해결 할 수 없었다. (아쉽)