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;
}
1. 괄호를 입력 받는다. 2. 괄호의 수 만큼 반복문을 돌린다. (여기에서 top는 0보다 크거나 같아야함.) (top가 0보다 작다는 말은 닫는 괄호가 여는 괄호보다 먼저 나왔다는 말이기 때문에 반복문 종료) 2-1) 만약 해당 문자가 '('라면 top++ 2-2) 만약 해당 문자가 ')'라면 top-- 3. 만약 top가 0이라면 (제대로 된 것) YES출력 4. top가 0이 아니라면(여는 괄호가 많거나, 닫는 괄호가 많거나, 닫히지 않았는데 열렸거나, 열리지 않았는데 닫힌 경우) NO
#include <stdio.h>
#include <string.h>
int main() {
int testcase;
char input[51];
int top = 0;
scanf("%d", &testcase);
while (testcase--) {
top = 0;
scanf("%s", &input);
for (int i = 0;top >= 0 && i<strlen(input); i++) {
if (input[i] == '(')
top++;
else if (input[i] == ')')
top--;
}
if (top == 0)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
