3986번: 좋은 단어 [C++]

3986번: 좋은 단어 (acmicpc.net)

3986번: 좋은 단어

좋은 단어 

다국어

한국어   

시간 제한           메모리 제한                   제출                          정답                   맞힌 사람              정답 비율

 

1 초

256 MB

13762

7452

6005

54.502%

문제

 

이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 깨고 말았다. 안타깝게도 자는 동안 키보드가 잘못 눌려서 보고서의 모든 글자가 A와 B로 바뀌어 버렸다! 그래서 평석이는 보고서 작성을 때려치우고 보고서에서 '좋은 단어'나 세보기로 마음 먹었다.

평석이는 단어 위로 아치형 곡선을 그어 같은 글자끼리(A는 A끼리, B는 B끼리) 쌍을 짓기로 하였다. 만약 선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝 지을수 있다면, 그 단어는 '좋은 단어'이다. 평석이가 '좋은 단어' 개수를 세는 것을 도와주자.

 

입력

첫째 줄에 단어의 수 N이 주어진다. (1 ≤ N ≤ 100)

다음 N개 줄에는 A와 B로만 이루어진 단어가 한 줄에 하나씩 주어진다. 단어의 길이는 2와 100,000사이이며, 모든 단어 길이의 합은 1,000,000을 넘지 않는다.

 

출력

첫째 줄에 좋은 단어의 수를 출력한다.

예제 입력 1 복사

3
ABAB
AABB
ABBA

예제 출력 1 복사

2

예제 입력 2 복사

3
AAA
AA
AB

예제 출력 2 복사

1

예제 입력 3 복사

1
ABBABB

예제 출력 3 복사

1

 

흐름

1번과 2번을 구분했지만 사실 팰린드롬도 서로 짝지어지므로 1번의 경우만 존재한다.

코드

#include <bits/stdc++.h>
using namespace std;
int n, ret=0;
string s;
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	//1. 입력받기 
	cin >> n;
	for(int i=0;i<n;i++){
		cin >> s;
		int length=s.length();
		//2. 좋은 단어인지 확인하기
		stack<char> st;
		if(length % 2!=0) continue; //2-1. 길이가 홀수이면 좋은 단어 아님 
		for(int j=0;j<length;j++){
			//스택에 아무것도 없으면 집어넣기 
			if(st.size()==0) {
				st.push(s[j]);
				continue;				
			}
			//2-2. 같은 단어가 붙어 있으면 pop 
			if(s[j] == st.top()){ 
				st.pop();
			}
			else { //이전 글자가 같은 단어 아니면 stack에 저장 
				st.push(s[j]);			
			}
		}
		//2-3. 다 짝지어지고 스택이 비어있으면 좋은 단어
		if(st.size()==0){
			ret++;
		}  
	}
	//3. 정답 출력 
	cout << ret << "\n";
	return 0;	
}

유의할 점

• 디버깅 시에 stack에 아무 원소도 들어가있지않은데 top을 접근하면 오류가 난다. (출력시 주의)
• 스택의 맨 위 원소는 front가 아닌 top()이다.
  • https://life-with-coding.tistory.com/406

[C++][STL] Stack 기본 사용법 및 예제

 

 

선생님 코드

#include <bits/stdc++.h>
using namespace std;
int n, ret;
string s;
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	//1. 문제 입력 
	cin >> n;
	for(int i=0;i<n;i++){
		cin >> s;
		stack<char> stk; //스택 지역변수로 선언(문자열마다 스택 따로 사용)
		//2. 문자를 스택에서 pop하거나 push 
		for(char a:s){
			if(stk.size() && stk.top()==a) stk.pop();
			else stk.push(a);
		}
		//3. 스택에 남는 단어가 없으면 좋은 단어 
		if(stk.size()==0) ret++;
	}
	//4. 출력하기 
	cout << ret << "\n";
}

포인트

• 위의 유의할 점에서도 말했지만 스택은 size를 체크하고=> top을 체크해야 레퍼런스 오류가 나지 않는다.(빈 공간 참조 막기)
• 문자열이 어떤식의 로직인지 모를때는 뒤집어보고 위아래로 적어보자.
• 겹치는 행동을 한다면 하나로 합치자.
• 지역변수 선언시에는 범위 잘 보기

짝짓기와 폭팔 => 스택을 사용하지 않을까 생각하기