[백준알고리즘] 1874번: 스택 수열 -Java

[백준알고리즘] 1874번: 스택 수열 -Java

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

1874번: 스택 수열

 

처음에 문제를 이해하는 데 이상했었다.

 

문제를 설명하자면 1부터 n까지의 수를 차례대로 stack에 push 하거나 pop 해서 주어진 수열을 만들 수 있는가를 물어보는 문제이다.

 

 

이에 대해서 문제를 풀기 위해서는 stack에 push할 때의 조건과 pop 시킬 때의 조건을 파악하면 된다.

 

일단 현재 필요한 수열의 수를 맞추기 위해서라도 pop하기 전에 push를 한다. 즉, push는 무조건 한다고 보면 된다.

 

하지만 pop에서는 좀 까다롭게 봐야한다. pop 할 때에는 stack이 비어있으면 안 되며, 수열을 인덱싱하며 현재 필요한 수를 가리키고 있을 때 그 값과 stack에 쌓여있는 맨 꼭대기의 값이 같을 때에만 pop을 시켜줘야 한다.

 

손으로 해보면 금방 이해되게 때문에 설명은 생략하겠다.

 

 

예전에 풀었던 문제인데 자바 연습할 겸 새로 풀어봤더니 이전에도 자바로 풀었던 문제였다.

 

그리고 계속 통과 못했던 게 Stack이나 ArrayList에 Integer로 넣어둔 것끼리 비교를 해서 문제가 발생했었다. Integer는 객체이기 때문에 ==과 같은 비교 연산자를 바로 쓰면 주소를 비교하기 때문에 값 비교가 안된다. 따라서 intValue()를 써줬다.

 

이외의 많은 틀릴만한 내용들을 정리한 게시글이 있어서 가져왔다.

https://www.acmicpc.net/board/view/22447

 

 

이번에 짠 코드는 다음과 같다.

import java.io.*;
import java.util.Stack;
import java.util.ArrayList;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		int i, t;
		ArrayList<Integer> input_list = new ArrayList<Integer>();
		Stack<Integer> stack = new Stack<Integer>();
		ArrayList<Character> result = new ArrayList<Character>();
		
		for(i = 0; i < N; i++) {
			input_list.add(Integer.parseInt(br.readLine()));
		}
		
		t = 0;
		for(i = 0; i < N; i++) {
			if(i + 1 <= input_list.get(t).intValue()) {
				stack.push(i + 1);
				result.add('+');
				
				while(t < input_list.size() && !stack.isEmpty() && stack.peek().intValue() == input_list.get(t).intValue()) {
					stack.pop();
					result.add('-');
					t++;
				}
			}
			
		}
		
		if(stack.isEmpty()) {
			for(i = 0; i < result.size(); i++) {
				System.out.println(result.get(i));
			}
		}
		else {
			System.out.println("NO");
		}
		
		return;
	}

}

 

 

이전에 짰던 코드는 아래와 같다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int t = Integer.parseInt(br.readLine().trim());
		Stack<Integer> stack = new Stack<Integer>();
		LinkedList<Integer> que = new LinkedList<Integer>();
		
		for(int i = 0; i < t; i++) que.add(Integer.parseInt(br.readLine().trim()));
		
		int k = 1;
		StringBuilder sb = new StringBuilder();
		
		while(!que.isEmpty()) {
			if(stack.isEmpty()) {
				stack.push(k);
				sb.append("+\n");
				k++;
			}
			
			int m = stack.peek();
			int n = que.peek();
			
			if(n > m) {
				stack.push(k);
				sb.append("+\n");
				k++;
			}else if(n == m) {
				que.poll();
				stack.pop();
				sb.append("-\n");
			}else {
				sb.replace(0, sb.length(), "NO");
				break;
			}
		}
		
		bw.write(sb.toString());
		
		bw.close();
		br.close();
	}

}

 

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다