[백준] 1874_스택 수열

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

1874번: 스택 수열

 

이 문제는 처음에 내가 이해를 잘 못했다.

수열로 뭐 하는거지? 뭐라는거야...

왜 입력이 8개인데 출력이 이렇게 많을까? 이랬는데 이해를 해보니깐 아. 탄성이 나왔다.

 

먼저 설명을 하자면,

백준 예제로 보자. 

입력이 

8 4 3 6 8 7 5 2 1

들어왔다.

처음의 8은 testcase수이다. 

그럼 4부터 봐야한다. 

(4 3 6 8 7 5 2 1) 

 

여기 문제에서 

"1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓으로써,,,"를 잘 봐야한다. 

이 말은 1부터 스택에 넣는데 원하는 수가 보이면 pop한다는 말이다. 

 

 

예시를 들어보자면,

4부터 해보자

 

4가 나오기 위해 push(1), push(2), push(3), push(4)를 해야하고, 4를 pop해서 꺼내와야 문제에서 말하느 수열을 만들 수가 있다. 

 

4를 만들기위해서는  push(1), push(2), push(3), push(4), pop(4)를 해야하기 때문에 ++++-가 되는 것이다. 

 

그렇다면, 이어서 4다음의 수 3을 해보자

 

4가 pop한 상태이기 때문에 스택의 꼭대기 층에는 3이 있다. 

3을 원하기 때문에 여기서는 pop(3)만 해주면 된다. 

 

 

이렇게 해서 이 수열을 만들기 위해서 +,-가 어떻게 들어가는지를 출력하는 것인데,

수열을 못 만들때는 NO를 입력해라고 한다. 

이 말이 무엇이냐면,

 

여기서 간단히 말하자면, 꼭대기에는 4가 있는데 3을 원할때이다. 

스택은 먼저들어오는 수가 나중에 나가는 구조이기 때문에

꼭대기의 수 부터 나가야 밑의 수가 나갈 수 있다.

다시말해 3이 나가려면 4가 꼭 pop해줘야 나갈 수 있다는 말이다. 

그래서 저 상태에서 3을 원한다면, 이것은 만들 수 없는 구조이기 때문에 NO를 출려해야한다. 

 

 

이 문제를 이해하고 나서 알고리즘을 짰다. 

은근 알고리즘은 쉬웠는데, 문제를 이해하기가 좀 당황했었다. 

알고리즘
1. 수를 입력받는다. 
2. 기억하는 숫자(1부터 n까지) ~ 입력 받은 수까지 반복한다. (어차피 원하는 수까지 push를 해야하기 때문)
   2-1) 스택에 저장한다. 
   2-1) +출력한다.
3. stack의 꼭대기의 수가 입력받은 수라면
   3-1) pop을 해준다. 
4. stack의 꼭대기의 수가 입력받은 수가 아니라면,
   4-1) 이것은 수열을 만들 수 없기 때문에 NO를 출력하고 break해준다. 

 

소스 코드

#include <stdio.h>
#include<stdbool.h>
int main() {
	int remember_number = 1;
	int testcase;
	int top = -1;
	int stack[100001];
	int number; 
	char answer[200000];
	int answer_count = 0;
	bool answer_check = true;


	scanf("%d", &testcase);

	for(int T = 0; T<testcase; T++){
		scanf("%d", &number);
		for (; remember_number <= number; remember_number++) {
			stack[++top] = remember_number;
			answer[answer_count++]= '+';
		}

			if (stack[top] == number) {
				--top;
				answer[answer_count++] = '-';
			}
			else {
				printf("NO");
				answer_check = false;
				break;
			}
	}
	if (answer_check) {
		for (int i = 0; i < answer_count; i++) {
			printf("%c\n", answer[i]);
		}
	}
	return 0;
}