중복 문자 제거/string::find

• 내 코드

중복만 생각하고 set썼다가 순서를 유지하지 못해서 그냥 answer 중복 검사를 했다.

string.find는 반환값이 int이고,  못 찾을 경우 end()가 아닌 string::npos(-1)이다. 

 

#include <string>
#include <vector>

using namespace std;

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

    for (char c : my_string)
    {
        if (string::npos == answer.find(c))
        {
            answer += c;
        }
    }

    return answer;
}

 

• 개선

set을 같이 사용해서 중복 검사에만 set을 이용한다.

탐색에 O(1) 이기에 총 시간 복잡도는 O(N)이 된다!

 

#include <string>
#include <vector>
#include <unordered_set>

using namespace std;

string solution(string my_string) {
    string answer = "";
    unordered_set<char> seen;

    for (char c : my_string) {
        if (seen.find(c) == seen.end()) {
            answer += c;
            seen.insert(c);
        }
    }

    return answer;
}