[백준 1874/Java] 스택 수열

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

1874번: 스택 수열

 

 

---

 

스택, 큐 사용해서 풀었는데 돌려보니 틀렸다고 뜸

근데 질문 게시판 확인하니 아래 같은 글이 있었다

글 내용대로 == 대신 equals() 함수 사용하니 통과 됐음

📌 -128~127의 범위를 벗어나는 값을 가진 Integer 객체를 == 연산자를 사용해 비교할 경우 예상과 다르게 동작한다고 한다.

 

📝 참고
https://www.acmicpc.net/board/view/125818

 

---

 

풀이

1. 수열 정보 저장할 Queue 객체 생성
   • 수열의 경우 입력받은 순서대로 스택의 top 값과 비교할 것이므로 FIFO 구조인 큐 사용
2. 스택으로 사용할 Stack 객체 생성
3. 첫 번째 for문은 큐에 수열 정보 저장
4. 두 번째 for문은 스택에 1부터 n까지의 값을 저장
   1. 스택에 값이 하나 저장될 때마다 큐와 스택의 값을 비교하는 while문 실행
   2. 스택이 비어있지 않고, 큐와 스택의 최상위 값이 같을 경우 큐, 스택에서 해당 값 삭제
   3. 이 때 스택과 큐엔 Integer 객체가 저장되어 있기 때문에 == 연산자 사용시 예상과 다르게 동작하므로 equals() 함수 사용해 비교할 것
5. for문이 끝난 후 스택이나 큐가 비어있지 않으면 수열을 못 만든 것이므로 NO 출력

 

코드

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int n = Integer.parseInt(br.readLine());
		Queue<Integer> arr = new LinkedList<Integer>();
		Stack<Integer> stack = new Stack<Integer>();
		
		// 수열 정보 저장
		for (int i=0; i<n; i++) {
			arr.offer(Integer.parseInt(br.readLine()));
		}
		
		// 스택에 오름차순으로 값 저장
		for (int i=1; i<=n; i++) {
			stack.push(i);
			sb.append("+\n");
			
			// 스택의 top 값과 큐의 첫 번째 값이 같으면 해당 값 삭제
			while (!stack.isEmpty() && arr.peek().equals(stack.peek())) {
				stack.pop();
				arr.poll();
				sb.append("-\n");
			}
		}
		
		// 스택이 비어있으면 수열이 잘 생성된 것
		if (!stack.isEmpty() || !arr.isEmpty())
			System.out.println("NO");
		else
			System.out.println(sb);
	}

}