c++ 16120번 PPAP (백준)

#include <cstdio>
#define M 1000000

class Stack { //Stack을 클래스로 
private:
	int top;
	char arr[M];
public:	
	Stack() : top(0){}
	bool isEmpty() { return top == 0;} //스택 비었는가? 
	void push(char e) {arr[top++] = e;} //스택 넣기 
	char pop() {return arr[--top];} //스택 꺼내기 
	int cnt() {return top;} //스택의 요소 개수 
	char peek() {return arr[top-1];} //가장 마지막에 들어간것 
};

int main(void) {
	char c[M] = {0};
	scanf("%s", c); //문자열 입력 
	Stack s;
	int i=0;
	bool flag = 0; 
	while(c[i] != '\0') { //Null 문자가 오면 반복문 종료 
		if(c[i] == 'P') { //P일 경우 
			if(s.isEmpty()) s.push(c[i]); //스택이 비어있으면 넣고 
			else if(s.peek() == 'P') s.push(c[i]); //가장 마지막에 들어간 것이 P여도 넣고 
			else { //가장 마지막이 A일 경우 스택의 요소 두개를 뺀다 
				s.pop();  //PPAP -> P이므로 
				s.pop(); //PPA(스택) + P(비교하는거); 여기선 스택에서 2개를 빼고, 비교하는 것을 집어넣지 않으면 PPAP => P 을만들수 있다. 
			}
		}
		else if(c[i] == 'A') { //비교하는게 A일 경우 
			if(s.cnt() < 2) { //PPAP문자열을 만들려면 반드시 스택에 P 2개는 스택에 있어야 한다.
				flag = true; //A를 스택에 넣지 못하여 끝났음을 나타내는 플래그이다. 
				break; //더 이상 반복을 할 필요가 없다 
			}  else { //P가 스택에 이미 2개이상이면 
				s.push(c[i]); //스택에 집어넣는다 
			}
		}
		i++;
	}
	
	if(s.cnt() == 1 && s.peek() == 'P' && !flag) printf("PPAP");
	else printf("NP");
}

 

 

풀이 : 스택

PPAP 문자열인지를 아닌지를 판단해야 한다.

 

1. 스택을 구현한다.

2. 문자열을 입력받는다

3. 하나하나씩 스택에 집어넣는다.

여기서 PPAP문자열은 PPAP -> P이므로

스택에 pop부분과 가장 가까운 곳이  ...PPA 의 형태이며 P가 스택에 들어갈려고 할 때 P를 스택에 넣지 않고, 스택에 있는 PA를 제거하면 PPAP -> P을 구현 할 수 있다.

 

P와 A을 집어넣을 땐

A의 경우는 스택의 요소가 2개이상 있어야 집어넣을 수 있다 (PP가 없다면 PPAP 문자열이 되지 않는다)

P의 경우는 스택에 아무것도 없을때도, 스택안에서 가장 최근 것이 P일때 집어넣을 수 있으며,

가장 최근 것이  A라면 스택이 상황이 ...PPA 인지를 확인 한 다음 , 맞으면 스택에서 두번 pop 한다.

 

4. 최종결정

PPAP문자열은 PPAP->P의 과정을 거치다 보면 결국 P하나만 남게된다! 그렇지 않은 것은 PPAP 문자열이 아니다.

이는 스택에 P 1개만 남아있으며, 반복문이 도중에 종료되지만 않았다면 PPAP문자열임을 알 수 있다.

 

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

16120번: PPAP