[백준/BOJ] 1874번 : 스택 수열 (JAVA / 자바)

안녕하세요~ 코딩하는 코알못 코메인입니다.

 

 

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

1874번: 스택 수열

---

- 문제 -

 

난이도 실버 3 문제이다.

자바에서 입력방식은 scanner와 bufferedreader가 있다.

자바를 초반에 접하면 처음에 배우는 입력은 scanner이다. scanner가 bufferedreader보다 편하지만 속도가 느리다.

bufferedreader는 무조건 문자열로 받아오기때문에 정수형이나 실수형 변수에 저장하기 위해서는 입력과 형변환을 해줘야한다.

더 자세한 내용은 아래 글 참고 하면 좋다.

https://comain.tistory.com/3

(JAVA / 자바) Scanner 와 Bufferedreader

 

풀이 방법

1~n(첫줄 입력값) 까지의 값을 push(자료를 넣다)과 pop(마지막 자료를 빼다)로 수열을 만드는 것이다.

예를 들어보자 1예제를 보면 n이 8이기 때문에 1~8까지다. 그리고 원하는 수열의 형태는 4, 3, 6, 8, 7, 5, 2, 1이다.

입력값을 stack과 비교해야하기에 입력값은 순서대로 배열에 저장해준다.

맨 처음으로 stack에서 나와야할 자료는 4이고, 그 다음엔 3, 6, 8, 7, 5, 2, 1 순으로 stack에서 빼야 한다는 것이다.

우선 4를 빼려면 1부터 4까지 다 들어가 있어야 한다. stack에 1부터 4까지 push한다. push할 경우 출력은 +이다.

우선 4개 push이기 때문에 ++++가 출력된다.

stack : 1,2,3,4. 4를 pop한다. stack : 1,2,3. 출력은 ++++-.

4다음에 빼야할 수는 3이다. stack의 마지막 수가 무엇이냐에 따라서 바뀐다.

마지막 수가 3보다 크다면 stack에는 3보다 더 큰 수가 들어가있다는 것이다. 그렇다면 3을 빼야하는데 뺄 수가 없으니 이것은 원하는 수열을 만들 수가 없다는 것이다. 그렇다면 여기서 반복을 종료하고, NO를 출력한다.

마지막 수가 3과 같다면 3을 pop한다. 그리고 -를 출력한다.

마지막 수가 3보다 작다면 다시 3까지 push해준다. 이 세가지의 경우를 매번 반복해준다.

stack : 1,2,3. 3을 pop한다. stack : 1,2. 출력은 ++++--

다음 값은 6이다. 마지막 값은 2. 6보다 작다. 6까지 push를 해준다.

stack : 1,2,5,6. 두개 push 했으니 출력은 ++++--++

stack : 1,2,5,6. 6을 pop한다. stack : 1,2,5. 출력은 +++--++-

다음 값은 8이다. 마지막 값인 5보다 크니 8가지 push

stack : 1,2,5,7,8. 두개 push 했으니 출력은 ++++--++-++

이번에 빼줄 값은 8인데 보면 남은 값과 stack에 남은 값은 역순으로 순서가 같다.

그렇다면 전부 빼주면 된다.(코드로는 하나씩 조건에 맞춰 뺏다. 설명 간략화를 위해 이렇게 설명한 것뿐이다)

stack은 비었고, 출력은 ++++--++-++-----이다. 예제 정답이랑 같다.

 

빠르게 예제 2번도 보고 코드로 넘어가자.

1~5이고, 원하는 수열은 1,2,5,3,4이다.

1까지 stack에 넣는다. 1을 빼준다. +-

2까지 stack에 넣는다. 2를 뺀다. +-+-

5까지 stack에 넣는다. 5를 뺀다. +-+-+++-

stack의 마지막 값은 4. 이번에 빼줄 값은 3. 위에서 말했던 마지막값이 빼줄 값보다 크다면 수열을 성립할 수 없다.

진행하던 반복을 종료하고, NO 출력.

 

+와 -의 출력값은 StringBuilder에 저장하고 마지막에 한번에 출력해 줄 것이다. 왜냐하면 예제 2번처럼 잘 가다가 수열 성립이 되지 않는것을 아는 경우엔 NO만 출력해야 하기 때문이다.

 

코드를 보자.

---

-풀이-

 

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		StringBuilder sb = new StringBuilder();
		//배열의 인덱스 값을 담당할 변수
		int index = 0;
		//1~n까지의 현재 값을 담당할 변수
		int num = 1;
		
		//입력값을 변수에 저장
		for(int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		Stack<Integer> stack = new Stack<Integer>();
		
		//n개의 값으로 수열을 만들기때문에 index는 0부터 n-1까지이기때문에 n보다 작은경우에 반복한다.
		while(index < n) {
			//stack이 비어있지 않다는 조건문을 꼭 넣어준다. 당연하다 stack에 머가 있어야 pop을 할테니
			if(!stack.empty() && arr[index] < stack.get(stack.size() - 1)) {
				break;
			}else if(!stack.empty() && arr[index] == stack.get(stack.size() - 1)) {
				stack.pop();
				sb.append("-").append("\n");
				index++;
			//push해줄때는 stack이 비어있어도 된다.
			}else {
				while(num <= n) {
					if(arr[index] != num) {
						stack.push(num);
						sb.append("+").append("\n");
						num++;
					}else {
						stack.push(num);
						sb.append("+").append("\n");
						num++;
						break;
					}
				}
			}
		}
		
		if(index == n) {
			System.out.println(sb);
		}else {
			System.out.println("NO");
		}
	}

}

---

-결과-

 

---

아직 코딩 공부가 부족한 필자라 설명과 풀이 방법이 많이 미흡할 수 있다. 코딩 고수분들은 보시고 문제점이 있다면 댓글로 말해주시면 감사한 마음으로 참고 수정 하겠습니다.