프로그래머스 - 신규 아이디 추천 - C++

https://school.programmers.co.kr/learn/courses/30/lessons/72410

프로그래머스

 

#include <string>
#include <vector>
#include <regex>

using namespace std;

string solution(string new_id) {
    string answer = "";

    // 대문자를 소문자로 치환
    for (int i = 0; i < new_id.length(); i++)
    {
        if (new_id[i] >= 'A' && new_id[i] <= 'Z')
            answer += new_id[i] + 32;
        if ((new_id[i] >= 'a' && new_id[i] <= 'z') || (new_id[i] >= '0' && new_id[i] <= '9'))
            answer += new_id[i];
        if (new_id[i] == '-' || new_id[i] == '_' || new_id[i] == '.')
            answer += new_id[i];
    }
    //3번
    int index = answer.find("..");
    while (index != string::npos)
    {
        answer = answer.replace(index, 2, ".");
        index = answer.find("..");
    }
    // 4번
    if (answer[0] == '.')
        answer.erase(0, 1);
    if (answer[answer.length()-1] == '.')
        answer.erase(answer.length()-1, 1);

    // 5번
    if (answer == "")
        answer += 'a';

    // 6번
    if (answer.length() >= 16)
        answer.erase(15);

    if (answer.back() == '.')
        answer.erase(answer.length() - 1, 1);

    // 7번
    if (answer.length() <= 2)
    {
        char c = answer.back();
        while (answer.length() <= 2)
        {
            answer += c;
        }
    }
    return answer;
}

 

이 문제는 주어진 아이디에 대해서 특정 규칙에 맞게 바꿔서 리턴하는 문제이다. 

규칙은 다음과 같다.

1단계 new_id의 모든 대문자를 대응되는 소문자로 치환합니다.
2단계 new_id에서 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.)를 제외한 모든 문자를 제거합니다.
3단계 new_id에서 마침표(.)가 2번 이상 연속된 부분을 하나의 마침표(.)로 치환합니다.
4단계 new_id에서 마침표(.)가 처음이나 끝에 위치한다면 제거합니다.
5단계 new_id가 빈 문자열이라면, new_id에 "a"를 대입합니다.
6단계 new_id의 길이가 16자 이상이면, new_id의 첫 15개의 문자를 제외한 나머지 문자들을 모두 제거합니다.
     만약 제거 후 마침표(.)가 new_id의 끝에 위치한다면 끝에 위치한 마침표(.) 문자를 제거합니다.
7단계 new_id의 길이가 2자 이하라면, new_id의 마지막 문자를 new_id의 길이가 3이 될 때까지 반복해서 끝에 붙입니다.

 

우선 1~2번 단계는 하나의 반복문에서 문자를 하나씩보며 answer에 대입하는 형식으로 구현했다. 

대문자는 소문자로 바꿔서 저장하고 숫자, 소문자, 빼기, 밑줄, 마침표는 그대로 저장한다.

나머지 문자는 저장하지 않음으로써 제거한다. 

 

3번의 경우 string 라이브러리에 있는 string.find 와 string.replace 함수를 사용하였다. 

 

4,5,6번은 string.erase 함수를 사용하여 구현했다.

 

7번은 while문을 통해 구현했다. 

 

보완할 점

여기서 비효율적인 부분이 3번의 구현이다. 

//3번
    int index = answer.find("..");
    while (index != string::npos)
    {
        answer = answer.replace(index, 2, ".");
        index = answer.find("..");
    }

find 함수를 통해 계속해서 처음부터 문자열을 검색한다. 

find의 오버로딩 중에서 어떤 index 부터 검색할 것인지에 대한 함수도 있다. 

 

index = answer.find("..",index);

따라서 이런식으로 구현하는 중복 검색을 방지한다. 

 

또는 

string ret;

new_id = ret;
ret.clear();

for (char& ch: new_id) {
    if (!ret.empty() && ret.back() == '.' && ch == '.') continue;
    ret += ch;
}

이런식의 방법이 있다. 

다른 사람의 풀이를 본건데 문자를 하나씩 보며 저장하고 현재보는 문자와 문자열의 마지막 문자가 .이면 현재 . 문자를 스킵한다. 따라서 자연스레 연속된 . 을 제거할 수 있다. 

 

위 두가지의 방식은 모두 O(n)의 시간 복잡도를 가지기 때문에 어떤 방법을 채택하든 괜찮다. 

다만 가독성 측면에서 첫번째 방법이 좀 더 유리하므로 첫번째를 선택하는 것이 좋아보인다. 

 

정규표현식

마지막은 문제를 보고 떠올랐지만 사용법을 몰라서 적용하지 못했던 방법이다. 

정규표현식은 문자열에서 특정 문자나 패턴을 파악할 때 사용하는 방식이다. 

 

https://tpree.tistory.com/117

 

#include <string>
#include <regex>

using namespace std;

string solution(string new_id) {
    // 1단계: 대문자를 소문자로 치환
    for (auto& ch : new_id) ch = tolower(ch);

    // 2단계: 소문자, 숫자, '-', '_', '.'를 제외한 문자 제거
    new_id = regex_replace(new_id, regex("[^a-z0-9-_.]"), "");

    // 3단계: 연속된 마침표를 하나의 마침표로 치환
    new_id = regex_replace(new_id, regex("[.]+"), ".");

    // 4단계: 마침표가 처음이나 끝에 위치하면 제거
    new_id = regex_replace(new_id, regex("^\\.|\\.$"), "");

    // 5단계: 빈 문자열이면 'a'를 추가
    if (new_id.empty()) new_id = "a";

    // 6단계: 16자 이상이면 첫 15자를 제외한 나머지 제거 후, 마지막 문자가 마침표이면 제거
    if (new_id.size() >= 16) {
        new_id = new_id.substr(0, 15);
        new_id = regex_replace(new_id, regex("\\.$"), "");
    }

    // 7단계: 길이가 2자 이하이면 마지막 문자를 길이가 3이 될 때까지 반복
    while (new_id.size() < 3) {
        new_id += new_id.back();
    }

    return new_id;
}

다음과 같이 정규표현식을 사용하면 수많은 if-else 구문대신 한줄로 표현할 수 있다.

 

이런 정규표현식은 내부적으로 최적화가 되어있어서 효율성 측면에서 일반적으로 효과적이며 

가독성이나 유지보수 측면에서 유리해서 일반적으로 추천되는 방법이라고 한다. 

 

앞서 말한 세 가지 방법 모두 O(n)의 시간 복잡도를 보이기 때문에 원하는 방법을 선택해도 좋을 것 같다.