[백준] 1874 스택 수열 - 스택 + 자료구조 JAVA

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

1874번: 스택 수열

코드설명

스택 자료구조를 활용하는 문제입니다.

 

문제로직입니다.

1. 문제에 targetN ( N 이하의 정수) 들이 주어집니다. 이떄, targetN 이 주어질때마다 Stack에 1부터 N까지의 값을 넣을 수 있도록 처리하면서 Stack에 우리가 찾고자하는 targetN이 있는지 매번 검색합니다.
2. 만약에 Stack에 넣는값이 우리가 넣고자하는 1부터 N까지의 값을 초과할시에는 해당 값을 push와 pop연산으로 찾을 수 없다는 의미이므로 아래의 코드로 종료시킵니다.

if(numValue > N+1) {
    System.out.println("NO");
    return ;
}

 

이 문제같은경우, 입력이 주어질떄마다 그때에 바로바로 Stack에 모든 값을 넣으면서 연산이 가능한지 찾아야합니다.

for문에 while(true)문을 넣어서 Stack에서 우리가 찾고자하는 targetN값을 찾을 수 있는지 알아내야합니다.

숫자가 주어질때마다 연산을 통해 바로바로 찾아야한다는것을 ( for문 안에 while문을 넣는다는 생각) 구현해야 풀 수 있는 문제입니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
	public static int N;
	public static int answer = 0;
	public static Stack<Integer> stack = new Stack<>();
	public static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	
    	int numValue = 1;
    	for(int i=1;i<=N;i++) {
    		st = new StringTokenizer(br.readLine());
    		int num = Integer.parseInt(st.nextToken());
    		
    		while(true) {
    			if(numValue > N+1) {
    				System.out.println("NO");
    				return ;
    			}
    			if(stack.isEmpty()) { //Stack에 아무값도 없다면 무조건 값을 넣어야합니다.
        			stack.push(numValue++);
        			sb.append("+").append("\n");
        		}
        		else if(!stack.isEmpty()) { //만약 Stack에 값이 존재할시에 
        			if(stack.peek() == num) { //현재 Stack의 최상단값과 출력하려는 값이 같으면 pop시키면서 출력합니다. 또한 pop시키면 stack에 값을 넣는 while문에서 break합니다.
            			stack.pop();
            			sb.append("-").append("\n");
            			break;
        			}
        			else { //현재 Stack의 최상단값과 출력하려는 값이 다르면 push합니다.
        				stack.push(numValue++);
        				sb.append("+").append("\n");
        			}
        		}	
    		}
    	}
    	System.out.println(sb.toString());
    	
    }
    
}