[백준/BOJ] 3986번 : 좋은 단어 _C/C++

3986번: 좋은 단어

 

 

>문제

 

>접근방법

   스택을 쓰면 될 것 같다. 만나는 글자와 top을 비교해보고 같으면 pop, 다르면 push 하도록

 

 

>알고리즘

   1. 입력 문자열 개수만큼 첫 번째 for문 반복

   2. 문자열을 배열 str[100001]에 입력받는다.

   3. 입력받은 문자열 길이만큼 두 번째 for문 반복

   4. 스택이 비어있으면 str[j]를 push 한다.

   5. 스택의 top과 str[j]가 같으면 pop, 다르면 push 한다.

   6. 두 번째 for문이 끝나고 스택이 비어있으면 좋은 문자를 만난 것이기 때문에 cnt 를 1 더해준다.

   7. 결과값으로 cnt 출력.

 

 

>코드

#include <stdio.h>
#include <stack>

using namespace std;

 /* 알고리즘
    스택을 이용
    만나는 글자와 top을 비교해보고 같으면 pop 다르면 push / s.empty이면 push
  */

int num;
char str[100001];
int i, j, cnt = 0;

int main(void){
    scanf("%d", &num);
	
	stack<char>s; //스택 생성

	for(i=0; i<num; i++){
    	scanf("%s", str);

		for(j=0; str[j] != 0; j++){
			if(!s.empty()){
				if(str[j] == s.top()){
					s.pop();
				}
				else{
					s.push(str[j]);
				}
			}
			else{
				s.push(str[j]);
			}
		}

		if(s.empty()){
			cnt++;
		}

		while(!s.empty()) // 스택 비우기
			s.pop();
	}
	printf("%d", cnt);
	return 0;
}

 

 

>결과

 

 

>결론 

문제 이해하는데 3분 정도 걸린듯. 첨엔 뭔 소린가 했네. 스택 생각하기 전까지는 규칙 찾는답시고 같은 문자 사이에는 0 포함 짝수의 문자가 있어야 함.. -> 애초에 입력값이 홀수이면 나쁜 단어임.. 이런 생각 했다가 스택으로 하는게 편할 것 같아서 일단 해보고 특수한 경우는 그때 가서 처리하자 싶었는데 다행스럽게도 바로 됐다. 굳.