[백준] 3986. 좋은 단어

: 자료구조 - silver 4

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

3986번: 좋은 단어

 

 

정답

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>

char word[100001];
char stack[100001];

int main() {
	int n, cnt=0;
	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		scanf("%s", word);
		if ((strlen(word)%2) != 0) continue;
		int top = -1;
		
		for (int j = 0; word[j] != '\0'; j++) {
			stack[++top] = word[j];
			if (top == 0) continue;
			if (stack[top - 1] == stack[top]) {
				stack[top] = '\0';
				stack[top-1] = '\0';
				top -= 2;
			}
		}
		if (top == -1) cnt++;
	}
	printf("%d", cnt);
	return 0;
}

 

---

해설

: 스택을 이용한다.

1. 입력된 문자열에서 한 글자씩 스택에 넣어보면서(push) 스택을 검사한다.
2. -> 스택의 top에 들어간 글자와 바로 아래 글자가 같으면 두 글자를 pop하고 top을 2 줄인다.
3. 마지막 글자까지 push해본 뒤 스택에 남아있는 글자가 없으면 (top==-1) 좋은 단어이다.

 

1. 단어를 담을 배열 하나, 스택으로 사용할 배열 하나를 선언한다.

string.h도 인클루드해준다. 길이가 홀수인 문자열은 어떻게 해도 마지막에 글자가 남게 되므로,

이를 미리 감별하기 위해 strlen이 필요하기 때문이다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>

char word[100001];
char stack[100001];

int main() {
	int n, cnt=0;
	scanf("%d", &n);

 

2. 단어의 길이를 2로 나눠보아 나머지가 0이 아니면(홀수) 좋은 단어가 아니므로 넘어간다.

단어길이가 짝수이면 감별이 필요하다. 먼저 top을 -1로 설정한 뒤, 안에서 한 번 더 반복문을 돌린다.

단어의 0번째 인덱스부터 공백 문자가 나오는 부분까지를 보는 것이다. 스택에 글자를 삽입하며 top을 1 늘린다.

글자를 삽입할 때마다 스택 안을 확인하는데, 스택에 글자가 단 하나 있을 때(top=0)일 때는 이 과정을 스킵한다.

스택의 top과 top-1에 있는 글자를 확인하고, 서로 같으면 비운다. (스택의 해당 인덱스를 널문자로 바꾸고 top -2)

이 과정을 반복하여 마지막 글자까지를 삽입한 뒤, 스택을 확인한다.

스택이 비어있다면 (top = -1) 이는 좋은 단어이므로 cnt를 올린다.

마지막에 cnt를 출력하면 된다.

	for (int i = 0; i < n; i++) {
		scanf("%s", word);
		if ((strlen(word)%2) != 0) continue;
		int top = -1;
		
		for (int j = 0; word[j] != '\0'; j++) {
			stack[++top] = word[j];
			if (top == 0) continue;
			if (stack[top - 1] == stack[top]) {
				stack[top] = '\0';
				stack[top-1] = '\0';
				top -= 2;
			}
		}
		if (top == -1) cnt++;
	}
	printf("%d", cnt);
	return 0;
}