[C++] 백준 2902번 - KMP는 왜 KMP일까?

문제

KMP 알고리즘이 KMP인 이유는 이를 만든 사람의 성이 Knuth, Morris, Prett이기 때문이다. 이렇게 알고리즘에는 발견한 사람의 성을 따서 이름을 붙이는 경우가 많다.
또 다른 예로, 유명한 비대칭 암호화 알고리즘 RSA는 이를 만든 사람의 이름이 Rivest, Shamir, Adleman이다.
사람들은 이렇게 사람 성이 들어간 알고리즘을 두 가지 형태로 부른다.
첫 번째는 성을 모두 쓰고, 이를 하이픈(-)으로 이어 붙인 것이다. 예를 들면, Knuth-Morris-Pratt이다. 이것을 긴 형태라고 부른다.두 번째로 짧은 형태는 만든 사람의 성의 첫 글자만 따서 부르는 것이다. 예를 들면, KMP이다.
동혁이는 매일매일 자신이 한 일을 모두 메모장에 적어놓는다. 잠을 자기 전에, 오늘 하루 무엇을 했는지 되새겨 보는 것으로 하루를 마감한다.
하루는 이 메모를 보던 중, 지금까지 긴 형태와 짧은 형태를 섞어서 적어 놓은 것을 발견했다.
이렇게 긴 형태로 하루 일을 기록하다가는 메모장 가격이 부담되어 파산될 것이 뻔하기 때문에, 앞으로는 짧은 형태로 기록하려고 한다.
긴 형태의 알고리즘 이름이 주어졌을 때, 이를 짧은 형태로 바꾸어 출력하는 프로그램을 작성하시오.

입력

입력은 한 줄로 이루어져 있고, 최대 100글자의 영어 알파벳 대문자, 소문자, 그리고 하이픈 ('-', 아스키코드 45)로만 이루어져 있다. 첫 번째 글자는 항상 대문자이다. 그리고, 하이픈 뒤에는 반드시 대문자이다. 그 외의 모든 문자는 모두 소문자이다.

출력

첫 줄에 짧은 형태 이름을 출력한다.

접근

1. string으로 문자열 입력받는다
2. 첫번째 원소출력
3. 반복문을 돌려서 하이픈을 찾는다
4. 찾은 하이픈의 바로 뒷자리 원소를 뽑는다?
5. 최종 출력

이렇게 순서대로 코드를 짰다

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> 
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

int main() {
    
    string str,ans,first;
    cin >> str;
    
    first = str.front();

    for (int i = 0; i < str.size(); i++) {
        if (str[i] == '-') {
            ans = str[i + 1];
            first.append(ans);
        }
    }

    cout << first;

    return 0;
}

리뷰

제일 먼저 string을 입력받아서 str에 저장했다 그리고 string함수인 .front()를써서 첫번째 원소를 뽑았다 첫번째 글자는 항상 대문자라는 조건이 있기 때문에!! 뽑은 단어는 새로운 string first변수에 저장했다

그리고 반복문을 돌려서 하이픈을 찾는다 하이픈 바로 뒤에는 반드시 대문자라는 조건이 있기 때문에 str[i+1]을 사용해서 대문자를 뽑았다. 처음에 내가 실수를 했는데 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> 
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

int main() {
    
    string str,ans,first;
    cin >> str;
    
    first = str.front();

    for (int i = 0; i < str.size(); i++) {
        if (str[i] == '-') {
            ans = str[i + 1];
    
        }
    }

    cout << first + ans;

    
    return 0;
}

이렇게 코드를 작성했다. 이렇게 작성할 경우 대문자가 두개밖에 없는 경우에는 제대로 출력이 되지만 대문자가 세개 이상이 되면 오류가 발생한다 어떤 오류가 발생하냐?

Knuth-Morris-Pratt

이렇게 입력을 하면

KP

이렇게 출력이 된다. 그러니까 처음에 M을 뽑아서 ans변수에 저장을 하고 다시 반복문을 돌릴때 두번째로 뽑힌 P가 또 ans변수에 들어옴으로써 m의 자리를 뺏고? 지가 차지한다. 그래서 m이 나오지 않았던것이다

한 5분정도 생각하다가 깨달았다 ㅋㅋ

그래서 코드를 수정했다 

대문자를 뽑아서 ans변수에 저장하고 .append함수를 통해 first변수에 합쳐줬다  이 함수를 쓰면 뒤에 바로 이어서 붙일 수 있어서 모든 대문자들을 빼먹지 않고 출력 할 수 있다 다행히 어디서 오류가 났는지 빨리 깨달아서 다행이다 

출처

2902번: KMP는 왜 KMP일까? (acmicpc.net)

2902번: KMP는 왜 KMP일까?