[탐욕법 - 문자열 다루기]

문제

TIP

1. 두 단어를 비교하여 같이 만들어주어야 할 때, 실제로 같이 만들어 줄 필요가 없다.

2. 두 단어를 비교할 때 단어를 실제로 줄이고 늘리고 할 필요 없이 단어 길이의 차이만큼 반복하거나 인덱스를 이동하므로써 해결 할 수 있는 경우가 많다.

CODE

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
int main() {
    int answer = 9999;
    string a;
    string b;
    cin >> a;
    cin >> b;
    int diffLength = b.size() - a.size();
    for(int i=0; i<=diffLength;i++) {
        int count = 0;
        for(int j=0; j<a.size(); j++){
            if(a[j] != b[j+i]){
                count++;
            }
        }
    answer = min(answer,count);
    }
    cout << answer;
    
    return 0;
}

 

문제

#include <iostream>
#include <string>
 
using namespace std;
 
string S, subS;
 
int main(void) {
    
        getline(cin, S);
        getline(cin, subS);
        if (subS.size() > S.size()) {
                 cout << 0 << "\n";
        } else {
                 int result = 0;
                 for (int i = 0; i < S.size() - subS.size() + 1; i++) {
                         bool same = true;
                         for (int j = 0; j < subS.size(); j++){
                                 if (S[i + j] != subS[j]) {
                                          same = false;
                                          break;
                                 }
                         }        
                         if (same) {
                                 result++;
                                 i += subS.size() - 1;
                         }
                 }
                 cout << result << "\n";
        }
        return 0;
}

 

문제

TIP

1. 앞 뒤의 공백이 문제가 되는 경우가 있다 trim 메소드의 사용법 혹은 지원하지 않는 경우 어떻게 구현할 것인지 고민하자.

2. 역시 실제로 자르거나 할 필요는 없다. 

CODE

#include <iostream>
#include <string>
using namespace std;
 
int main(void) {
        string target;
        
        getline(cin,target);
                
        int targetLength = target.length();
        int wordLength = 1;
        
        
        
        for(int i = 0; i<target.size(); i++) {
            if(target.at(i) == ' ') {
                wordLength++;
            }
        }
        
        for(int i = 0; i<target.size(); i++) {
            if(target.at(i) != ' ') {
                break;
            }
            wordLength--;
        }
        
        for(int i = target.size()-1; i>=0; i--) {
            if(target.at(i) != ' ') {
                break;
            }
            wordLength--;
        }
        
        cout <<wordLength;
        return 0;
}