[cpp 알고리즘] 백준 19844 단어 개수 세기

[백준] 19844 단어 개수 세기 cpp 풀이

알고리즘: 구현, 문자열

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

 

문제 요약

문제가 너무... 어렵게 적혀있는 것 같다. 해야하는 것을 쉽게 정리하자면

• 먼저 띄어쓰기와 -(하이픈)을 기준으로 “단어”를 쪼갠다.
• 각각의 “단어”에서, 위처럼 줄어들었을 가능성이 있는 경우(즉, c', j', n', m', t', s', l', d', qu'로 시작하고 어포스트로피 뒤 글자가 모음인 경우) 이 단어들을 한 번 더 분리해 준다.

핵심은 여기서 '(어포스트로피) 앞에는 단어(c,j,n,m,t,s,l,d,qu) 가 있어야 하고, '(어포스트로피) 뒤에는 모음(a,e,i,o,u,h)로 시작하는 단어가 오면 된다. =>  ' 앞에는 단어 단위로, ' 뒤에는 한 글자만 확인하면 된다. 

 

아래의 예제로 보면,

qu'est-ce qu'il mange aujourd'hui

 

(1) 띄어쓰기와 하이픈을 기준으로 qu'est, ce, qu'il, mange, aujourd'hui 5개의 단어로 분리할 수 있다. 

(2) '(어포스트로피)가 있는 단어를 보면, qu'est는 ' 앞에 qu 단어가 있고, 뒤에는 모음 e로 시작하기 때문에 원래 2개의 단어였다. 

qu'il 단어도 앞에 qu가 있고, 뒤에는 모음 i로 시작하기 때문에 원래 2개의 단어이다. 하지만 aujourd'hui는 앞 단어가 aujourd 이기 때문에 조건을 만족하지 못해서 총 7개의 단어로 분리할 수 있다.

=> aujourd'hui 에서 ' 앞에 d가 나온다고 줄일 수 있는 게 아니다. ' 앞에는 단어 단위로, ' 뒤에는 한 글자만 확인하면 된다. 

풀이 정리

(1) 띄어쓰기를 포함해서 전체 문자열을 입력 받는다. 

(2) 띄어쓰기와 -(하이픈)을 기준으로 단어를 쪼갠다. 

(3) 쪼갠 단어 중에서, '가 있는 단어를 검사한다.

(3-1) ' 의 앞 단어가 (c,j,n,m,t,s,l,d,qu) 중에 있고, '의 뒤 한 글자가 모음(a,e,i,o,u,h) 라면 단어를 하나 더 쪼갤 수 있다.

C++ 코드 - 처음 작성한 코드

#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<string> v;
string s;

// 앞 단어가 ce, je, ne, me, te, se, le, la, de, que, si 이고 뒤 단어가 a,e,o,i,u,h 로 시작하면 앞 단어의 마지막 모음이 사라지고 '가 붙으면서 이어진다

int main(){
    
    getline(cin, s);
    
    // (1) 띄어쓰기나 -단위로 단어 구분
    string temp = "";
    for(int i=0; i<s.length(); i++){
        if(i==s.length()-1){
        	temp+=s[i];
            v.push_back(temp);
        } 
        if(s[i] == ' ' || s[i] == '-'){
            v.push_back(temp);
            temp = "";
        }
        else{
            temp += s[i];
        }
    }
    
    int ans = v.size();
    
    // (2) c', j', n', m', t', s', l', d', qu'로 시작
    for(int i=0; i<v.size(); i++){
        string temp2 = v[i];
        int findIdx = temp2.find("'");
        if(findIdx >= 0){
            string begin = "";
            for(int j=0; j<findIdx; j++){
                begin += temp2[j];
            }
            if(begin == "c" || begin == "j" || begin == "n" || begin == "m" || begin == "t" || begin == "s" || begin == "l" || begin == "d" || begin == "qu"){
                if(temp2[findIdx+1] == 'a' || temp2[findIdx+1] == 'e' || temp2[findIdx+1] == 'i' || temp2[findIdx+1] == 'o' || temp2[findIdx+1] == 'u' || temp2[findIdx+1] == 'h'){
                    ans++;
                }
            }
        }
    }
    cout << ans;
    
    return 0;
}

 

- 처음에는 '를 포함하는 지 확인하기 위해서, contains 함수를 이용하려고 했지만 C++에는 해당 함수가 없었다. 

대신에 find() 함수를 사용했다. find() 함수는 해당 문자가 있다면 해당 인덱스를, 없다면 -1을 반환한다. 

 

-  띄어쓰기 기준 단어를 저장하고 있는데 v 에서 한 단어(temp2) 씩 꺼낸다. 

- '의 인덱스를 찾고, 그 앞에는 단어(begin)으로 만들고 그 뒤에는 한 글자(findIdx+1)만 확인한다.

C++ 코드 - 배열 안에서 단어 비교

- (기존) if문에서 or 조건을 활용하여 비교

- (더 나은 방법) 배열 안에 넣어두고 비교: 근데 막상 하고 보니까 비슷한 것 같다.

string words[]={"c", "j", "n", "m", "t", "s", "l", "l", "d", "qu"};
char vowels[]= {'a','e','i','o','u','h'};

// 문자열이 배열에 있는지 확인하는 함수
bool isInWords(string str, string words[], int size) {
    for (int i = 0; i < size; i++) {
        if (str == words[i]) {
            return true;
        }
    }
    return false;
}

// 문자가 배열에 있는지 확인하는 함수
bool isInVowels(char c, char vowels[], int size) {
    for (int i = 0; i < size; i++) {
        if (c == vowels[i]) {
            return true;
        }
    }
    return false;
}

int main(){
    
    for(int i=0; i<v.size(); i++){
        string temp2 = v[i];
        int findIdx = temp2.find("'");
        
        if(findIdx >= 0){
        	string begin = "";
            for(int j=0; j<findIdx; j++){
                begin += temp2[j];
            }
        
            int wordsSize = sizeof(words) / sizeof(words[0]);
            int vowelsSize = sizeof(vowels) / sizeof(vowels[0]);

            if (isInWords(begin, words, wordsSize)) {
                if (isInVowels(temp2[findIdx + 1], vowels, vowelsSize)) {
                    ans++;
                }
            } 
        }
    }
    
    return 0;
}

 

7%에서 틀렸습니다

- 계속 틀렸습니다가 나와서 어떤 문제인지 원인을 못 찾고 있었는데, 정말 황당하게 입력받을 때 실수한 거였다. 

- 아래가 기존의 잘못 쓴 코드이다... 오류가 난 이유는 s.length()-1 (즉 마지막 알파벳은 temp 문자열에 추가되지 않는 점이었다...)

string temp = ""; 
for(int i=0; i<s.length(); i++){ 
	if(i==s.length()-1){ 
            v.push_back(temp);
    	} 
	if(s[i] == ' ' || s[i] == '-'){ 
            v.push_back(temp); temp = ""; 
    	} 
	else{ 
            temp += s[i]; 
    	} 
}

 

- 아래와 같이 수정해 주면 된다.

- 앞으로는 이런 실수를 하지 않도록, 아예 for문 밖에서 vector에 temp을 넣는 방식을 이용하거나, if-else 문 이후에 마지막 글자인지를 확인해야겠다. 

string temp = ""; 
for(int i=0; i<s.length(); i++){ 
    if(i==s.length()-1){ 
            temp += s[i]; 
            v.push_back(temp);
    } 
    if(s[i] == ' ' || s[i] == '-'){ 
            v.push_back(temp); temp = ""; 
    } 
    else{ 
            temp += s[i]; 
    } 
}

 

그리고, 중간에서 틀렸습니다가 나오면 입/출력도 다시 확인해봐야겠다.