[백준알고리즘-JAVA]1874번 풀이(스택 수열) - 초보도 이해하는 풀이

안녕하세요

인포돈 입니다.

백준 알고리즘 1874번 풀이입니다. 

* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 1874 (스택 수열)

문제

스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push push 하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

입력

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

출력

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

입력, 출력 예제

성공 코드

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 {

	static int T;
	static StringBuilder sb = new StringBuilder();
	static int temp = 1;
	static boolean err = false;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		T = Integer.parseInt(br.readLine());
		
		Stack<Integer> stack = new Stack<>();

		for(int i = 0 ; i < T ; i++) {
			int N = Integer.parseInt(br.readLine());
			
			for( ; temp <= N ; temp++) {
				stack.push(temp);
				sb.append("+").append("\n");
			}
			
			if(stack.peek()==N) {
				stack.pop();
				sb.append("-").append("\n");
			}else {
				err = true;
			}
		}
		
		if(err)
			System.out.println("NO");
		else
			System.out.println(sb);
		}
}

이번 알고리즘은 문제의 이해를 잘해야 합니다. 문제를 이해했다면, 어떠한 방법으로 구현 해할지를 구상해야 하는데 저 같은 경우 이 구현 방법이 안 떠올라 고생했었습니다. ㅜ

 

STEP을 따라가 보면서 문제의 이해부터 구현까지 이해해보도록 합시다.

---

알고리즘 흐름도

 입력받기 -> PUSH 하기 -> 원하는 수 자면 POP 하기 -> 만약 해당 숫자가 못 나온다면 NO출력 -> 모두 출력했다면 YES출력

---

STEP1 문제 이해하기

 구현에 앞서서 어떠한 문제인지 한번 깊게 생각해볼 필요가 있습니다. 우선 문제에서는 1부터 N까지의 수를 스택에 넣었다가 뽑는다고 합니다. 이때 스택에 PUSH 하는 순서는 반듯이 오름차순이라고 합니다.

 

만약 입력값이 8이라면

 1 2 3 4 5 6 7 8 이런 식으로 PUSH가 되어야 한다는 의미겠죠.

 

이때 입력으로 임의의 수열을 주었을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지를 파악해야 합니다.

 

자! 그렇다면 만약에 입력이 아래와 같다고 가정해 봅시다.

5
4
2
3
1
5

이런 입력이라면 어떠한 출력이 나와야 할까요?

 

하나씩 해봅시다. 4를 꺼내기 위해서는 우선 4개를 PUSH 해야겠죠?

 

STACK - 1

STACK - 1 2

STACK - 1 2 3

STACK - 1 2 3 4

이제 4가 나왔으니 POP을 해줍니다.

STACK - 1 2 3

이제 찾을 수는 2입니다. 그런데 앞에 3이 있네요? 어쩔 수 없이 POP을 해줍니다.

STACK - 1 2

이제 2를 찾았으니 POP을 해줍니다.

STACK - 1

이제 3을 찾아야 하는데 우리가 앞서 4까지 PUSH를 했기에 오름차순으로 PUSH 하기 위해서는 5의 숫자를 넣어주어야 합니다. 

STACK - 1 5 

??? 그러면 이미 눈치채셨기에 3은 더 이상 찾을 수 없는 수가 되어버립니다.

 

이에 따라서 출력은 "NO"가 출력이 되게 됩니다.

 

이러한 방식으로 우리는 문제를 이해해야 합니다.

---

STEP2 원하는 숫자가 나올 때까지 PUSH 해주기

		for(int i = 0 ; i < T ; i++) {
			int N = Integer.parseInt(br.readLine());
			
			for( ; temp <= N ; temp++) {
				stack.push(temp);
				sb.append("+").append("\n");
			}

		}

해당 식은 아주 쉽습니다. 물론 TEMP는 전역 변수로 초기값을 1로 설정해줍니다.

1부터 입력으로 들어온 값이 나올 때까지 push를 해줍니다. 

push를 했다면, sb(StringBuilder)에 "+"를 추가해 줍니다.

 

아주 간단하죠?

---

STEP 3 해당 숫자가 까지 나왔다면, 그 숫자 pop 해주기

		for(int i = 0 ; i < T ; i++) {
			int N = Integer.parseInt(br.readLine());
			
			for( ; temp <= N ; temp++) {
				stack.push(temp);
				sb.append("+").append("\n");
			}
			
			if(stack.peek()==N) {
				stack.pop();
				sb.append("-").append("\n");
			}
		}

해당 식 또한 간단합니다. 만약 stack의 꼭대기에 있는 값이 입력으로 들어온 수열의 값과 일치한다면 POP을 해줍니다.

(여기서 IF문을 활용한 이유는 해당 값이 아닐 수도 있습니다. 이러한 경우가 바로 오류의 상항 우리가 예외처리를 해주어야 하는 NO의 상황이 됩니다.

 

		for(int i = 0 ; i < T ; i++) {
			int N = Integer.parseInt(br.readLine());
			
			for( ; temp <= N ; temp++) {
				stack.push(temp);
				sb.append("+").append("\n");
			}
			
			if(stack.peek()==N) {
				stack.pop();
				sb.append("-").append("\n");
			}else {
				err = true;
			}
			
			
		}

아주 간단하게 ELSE면 err로 flag변수를 선언해주어 true로 변경해줍니다.

(이제 와서 다시 생각해보니 err가 true가 된다면 바로 해당 for문을 빠져나가게 break문을 작성해주어 더욱 효율적으로 코딩할 수도 있었겠다는 생각이 듭니다.)

 

이해가 잘 안 가시는 분들을 위하여 간단히 입력 예제 1번을 토대로 수행 겨로 가를 표시하면 아래와 같습니다.

		stack	출력결과
4	push - 1	1	+
	push - 2	1, 2	+
	push - 3	1, 2, 3	+
	push - 4	1, 2, 3, 4	+
	pop	1, 2, 3	-
3	pop	1, 2	-
6	push - 5	1, 2, 5	+
	push - 6	1, 2, 5, 6	+
	pop	1, 2, 5	-
8	push - 7	1, 2, 5, 7	+
	push - 8	1, 2, 5, 7, 8	+
	pop	1, 2, 5, 7	-
7	pop	1, 2, 5	-
5	pop	1, 2	-
2	pop	1	-
1	pop	-	-

이런 식으로  로직이 수행하게 되게 되죠

---

STEP 4 출력하기

		
		if(err)
			System.out.println("NO");
		else
			System.out.println(sb);

		}

뭐 출력은 앞서 flag값으로 준 err가 true라면 no를 출력해주고 아니라면 sb값을 출력해준다면 끝이 나는 문제!!

---