[BaekJoon 4659] 비밀번호 발음하기

오늘은 오랜만에 재미있는 문제가 있어서 한번 가져와 보았습니다. 

(코딩 테스트 준비 재밌....)

 

바로 백준 4659 비밀번호 발음하기라는 문제입니다.

 

저번 학기에 제가 본 코딩 테스트 결과를 보았을 때 확실히 제가 문자열 부분이 조금 약한 듯해서 관련 문제를 여러 개 풀어보고 있습니다.

 

여담은 여기까지 하고 문제를 읽어볼게요!

 

해당 문제는 이 링크에서 확인하실 수 있습니다.

 

 

솔직히 분류는 문자열이긴 한데, 단순 구현 문제와 비슷합니다.

 

제가 문제를 보고 떠오른 생각은 다음과 같습니다.

 

1. c++ string.find() 메소드를 확인해서 a, e, i, o, u 가 있는지 없는지 확인

 

2. 1에서 하나라도 존재한다면, 이제 for loop를 돌며 연속하는 3개의 자음이 있는지, 3개의 모음이 있는지 확인

방법 -> for문을 1부터 string size -1까지 돌며

string[i - 1], string[i], string[i + 1]를 각각 비교

 

3. 2번까지 통과했다면 다시 for loop를 돌며 연속하는 두 개의 문자가 있는지 확인

방법 -> for문을 1부터 string size까지 돌며

string[i - 1], string[i] 비교하고, "ee" "oo"가 아닌지 확인

 

1, 2, 3 모두 해당이 되지 않는다면 통과!

 

<소스코드>

#include <bits/stdc++.h>

using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	while(1){
		string inp;
		cin >> inp;
		if(inp=="end") break;
		
		if(inp.find("a")==string::npos 
			&& inp.find("e")==string::npos && inp.find("i")==string::npos
			&& inp.find("o")==string::npos && inp.find("u")==string::npos) {
		 	cout << "<" << inp << ">" << " is not acceptable.\n";
		 	continue;
		}
		
		bool second_condition=false;
		for(int i = 1; i < inp.size() - 1; i++) {	
			int co_cnt = 0, vo_cnt = 0;
			
			if(inp[i-1] == 'a' || inp[i-1] == 'e' || inp[i-1] == 'i' || inp[i-1] == 'o' || inp[i-1] == 'u') vo_cnt++;
			else co_cnt++;
			
			if(inp[i] == 'a' || inp[i] == 'e' || inp[i] == 'i' || inp[i] == 'o' || inp[i] == 'u') vo_cnt++;
			else co_cnt++;
			
			if(inp[i+1] == 'a' || inp[i+1] == 'e' || inp[i+1] == 'i' || inp[i+1] == 'o' || inp[i+1] == 'u') vo_cnt++;
			else co_cnt++;
			
			if(vo_cnt == 3 || co_cnt == 3) {
				second_condition=true;
		 		break;
			}
		}
		if(second_condition) {
			cout << "<" << inp << ">" << " is not acceptable.\n";
			continue;
		}
		
		bool serial = false;
		for(int i = 1; i < inp.size(); i++) {
			string comp="";
			comp+=inp[i-1], comp+=inp[i];
			if(inp[i-1] == inp[i]) {
				if(comp=="ee" || comp=="oo") continue;	
				serial=true;
		 		break;
			}
		}
		if(serial)	cout << "<" << inp << ">" << " is not acceptable.\n";
		else cout << "<" << inp << ">" << " is acceptable.\n";
	}
	return 0;
}

 

실제로 위 코드는 ac를 받았습니다.

 

근데 실제 시험이라면 맞았으면 넘어가겠지만 공부하는 단계이니까 조금 더 고민을 해보겠습니다.

 

사실 위 코드는 굉장히 별로인 게, 최악의 경우 

 

1번 조건에서 iterator가 내부적으로 begin()부터 end()까지 string의 길이만큼 이동하기 때문에 (n)에 비례하는 연산을 진행합니다.

 

a e i o u 다섯 개의 문자에 대하여 진행하니까 5번 루프를 도는 것과 비슷하죠.

 

그리고 2번, 3번 조건에서 각각 for loop를 사용하고 있기 때문에 결과적으로 7번 정도의 for 문을 사용하는 것과 비슷합니다. 

 

따라서 본 풀이를 최소의 루프로 진행하는 방법에 대해 고민해 볼 필요가 있습니다.

 

우선 새로운 소스코드는 다음과 같습니다.

 

<소스코드>

#include <bits/stdc++.h>

using namespace std;

string input;
int cnt[30], lcnt, vcnt;
bool isVowel(int idx) {
	return ( idx==0 || idx==4 || idx==8 || idx==14 || idx==20 );
}
int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	while(1){
		cin >> input;
		if(input=="end") break;
		fill(cnt, cnt+30, 0);
		vcnt=0, lcnt=0;
		bool non_acceptable = false;
		for(int i = 0; i < input.size(); i++) {
			int idx = input[i]-'a';
			cnt[idx]++;
			
			if(isVowel(idx)) vcnt++, lcnt=0;
			else lcnt++, vcnt=0;
			if(lcnt==3 || vcnt==3){
				non_acceptable=true; break;	
			}  
			
			if(i >= 1) {
				if(input[i-1] == input[i] && (idx != 4 && idx != 14)){
					non_acceptable=true; break;	
				} 
			}	
		}
		
		if(cnt[0]==0 && cnt[4]==0 && cnt[8]==0 && cnt[14]==0 && cnt[20]==0) non_acceptable=true;	
		
		if(non_acceptable) cout << "<" << input << ">" << " is not acceptable.\n";
		else cout << "<" << input << ">" << " is acceptable.\n";
	}
	return 0;
}

 

우선 각 string의 자릿수를 아스키코드로 변환해줍니다. 테스트 케이스는 대문자를 표현하지 않는다고 했으므로 저희는 'a', 'b' ~~ 'z' 까지만 0, 1 ~ 로 각각 매핑해주면 됩니다. 넉넉하게 30 정도면 모두 포함할 수 있습니다.

 

그리고 cnt라는 배열에 해당 알파벳의 숫자가 등장하면 해당 인덱스의 값을 증가시켜줍니다.

 

이렇게 되면 루프가 종료될 때 각 모음에 해당하는 cnt배열의 값만 0인지 아닌지 확인하여 1번 조건을 통과할 수 있습니다.

 

그리고 모음인지 확인해주는 함수를 간단히 짜서 활용합니다. 각 모음 a, e, i, o, u는 0, 4, 8, 14, 20에 해당됩니다. 

 

모음이면 lcnt = 0으로 바꾸고 vcnt만 증가시켜줍니다. 이렇게 되면 각각 lcnt, vcnt가 연속된 경우만 셀 수 있게 됩니다.

 

마지막으로 i>=1인 경우 input[i-1]과 input[i]를 비교하고, 같다면 idx가 e와 o에 해당하지 않는지 확인해줍니다. 

 

위 방법으로 모든 조건을 확인하고 통과할 수 있습니다.

 

 

*저의 글에 대한 피드백이나 지적은 언제나 환영합니다.