[백준 알고리즘 자바] 1874 : 스택 수열

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

1874번: 스택 수열

---

문제

• 스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 
• 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.
• 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 
• 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 
• 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 
• 이를 계산하는 프로그램을 작성하라.

입력

• 첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 
• 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다.
• 물론 같은 정수가 두 번 나오는 일은 없다.

출력

• 입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

입출력 예제

 

---

풀이방식

이번 문제는 Stack을 사용하여 푸는 문제이다.

 

문제가 어려웠으므로 이에 대한 이해부터 해보자.

처음 N은 1부터 N까지의 수를 의미한다. 8이라는 값이 입력되었으면, 1~8까지의 수가 입력되어야 한다.

8을 입력받았으니, 총 8개의 정수를 중복없이 입력해야 한다.

 

처음 입력받은 숫자는 4이다. 이는 즉 1부터 4까지의 수열을 만들어야 한다는 것이다.

스택이 비어있는 상태이므로 1,2,3,4 총 4번의 push가 이루어져야 하기에 +가 4번 출력되어야 한다.

그 후에 4라는 값을 스택에서 찾고, 있으면 그 값을 뺀다.

이를 통해 결과적으로 4라는 값을 입력받으면 +가 4번, -가 1번 출력되어야 하는 것이다.

스택에는 1,2,3 이 남아있고, ' + + + + -  ' 가 출력값에 추가된다.

그림으로 보면 아래와 같다.

다음으로 3을 입력받았다.

스택 최상단에서 3을 찾았으므로 3을 제거한다.

여기까지의 결과값은 ' + + + + -  - ' 이다.

6을 입력받으면 6까지의 수를 스택에 넣는다.

다만, 3과 4는 이미 제거되었으므로 제외한다.

6까지 넣은 후에 6이라는 수를 찾았으므로 이를 스택에서 제거한다.

여기까지의 결과값은 ' + + + + -  - + + - '  이다.

 

8을 입력받으면 6까지의 수를 스택에 넣는다.

다만, 3, 4, 6은 이미 제거되었으므로 제외한다.

마찬가지로 8을 제거한다.

여기까지의 결과값은 ' + + + + -  - + + - + + - '  이다.

다음으로 7을 입력받았다.

스택 최상단에 있는 7을 제거한다.

여기까지의 결과값은 ' + + + + -  - + + - + + - - '  이다.

다음으로 5을 입력받았다.

스택 최상단에 있는 5를 제거한다.

여기까지의 결과값은 ' + + + + -  - + + - + + - - - '  이다.

다음으로 2을 입력받았다.

스택 최상단에 있는 2를 제거한다.

여기까지의 결과값은 ' + + + + -  - + + - + + - - -'  이다.

다음으로 1을 입력받았다.

스택 최상단에 있는 1를 제거한다.

결과값은 ' + + + + -  - + + - + + - - - -'  이다.

이제 코드 작성으로 넘어가보자.

---

설계과정

1. 원하는 숫자까지 스택에 값을 넣고, +를 출력한다.

2. 원하는 숫자가 나오면 스택에서 해당 숫자를 빼고, -를 출력한다.

3. 다음 수열의 시작 값을 해당 숫자로 변경한다.

4. 스택 최상단 값이 입력받은 값이 아니라면 수열을 만들 수 없으므로 NO를 리턴한다.

---

풀이과정

1. BufferedReader 를 사용하고 문제를 풀기 위한 각 변수를 선언한다.

• StringBuilder : String과 문자열을 더할 때 새로운 객체를 생성하지 않고 기존의 데이터에 더하는 방식이다.
• N : 입력받는 정수
• start : 수열을 시작하는 값
• value : 입력받는 값

2. N이 0이 되기 전까지 도는 while문을 선언한다.

• N 까지의 수가 들어가있는 수열이기에, N만큼만 돈다.
• for 문으로 대체 가능하다.

3. value가 start 보다 크면 시작값 + 1 부터 입력받은 값까지를 스택에 넣고, +를 StringBuilder에 넣는다.

• 입력받은 값이 시작하는 값보다 크면 값을 넣을 수 있다.
• 예를 들어 value 가 5, start 가 3 이면 스택에는 4, 5를 넣을 수 있다.

4. 스택에 수를 다 넣었으면 start 변수에 value 값을 넣는다.

• 이미 입력받은 수는 중복이 불가능하다. 그러므로 입력받은 수 만큼의 값을 넣지 않기 위해 해당 코드를 작성한다.
• 예를 들어 3이 한번 입력된 후에, 5라는 값을 입력받았다고 해보자.
• 그러면 1,2,3 이 이미 스택에 들어있기에 이 값은 다시 입력되어서는 안된다.
• 즉, 앞으로는 4 이상의 값만 스택에 넣을 수 있다.

5. value가 스택 최상단의 값과 동일하지 않다면 NO를 리턴한다.

• peek() : 스택에서 가장 상단의 값을 리턴받는다. 단, pop와 달리 값을 꺼내지 않고 단순히 읽는다.
• 스택 최상단 값이 입력받은 값이 아니라면 수열을 만들 수 없으므로 NO를 리턴한다.
• 예를 들어 stack.peek()가 5 이고, value 가 3 이라면 3이라는 값은 for문을 통해 이미 지워진 값이므로 수열을 만들 수 없다.

5. 위 조건들이 전부 아니라면 스택에서 값을 제거하고, -를 StringBuilder에 넣는다.

• pop() : 스택에서 값을 제거한다.
• 스택 최상단과 value가 동일하면 스택에서 값을 제거한다.

6. StringBuilder에 저장된 +, - 를 출력한다.

---

답안소스

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 NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		Stack<Integer> stack = new Stack<>();
		int N = Integer.parseInt(br.readLine());
		int start = 0;
		
		while(N-- > 0) {
			int value = Integer.parseInt(br.readLine());
			
			if(value > start) {
				for(int i=start+1; i<= value; i++) {
					stack.push(i);
					sb.append("+\n");
				}
				start = value;
			} else if(stack.peek() != value) {
				System.out.println("NO");
				return;
			}
			stack.pop();
			sb.append("-\n");
		}
		
		System.out.println(sb);
	}
}