[String/C++] Leetcode _ First Unique Character in a String

 

🔎 문제 

문자열 s에서 중복되지 않은 첫 번째 원소의 위치를 출력하는 문제이다.

 

나의 풀이

문자의 개수를 카운트 해야해서 hashmap을 떠올렸고,

원소의 위치를 출력해야해서 고민 좀 했다.

하지만 만들어놓은 해시맵을 다시 탐색하면서 해시맵의 값이 0이면 그 때의 i값을 출력하는 방식으로 구현을 했다. 

요즘 자신감이 너무 떨어져서 그런지 이런 문제에도 쉽게 쪼는 것 같다. 힝

class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<int,int> hMap; 
        for (int i=0;i<s.size();++i){
            hMap[s[i]]++;
        }
        for (int i=0;i<s.size();++i){
            if (hMap[s[i]]==1){
                return i;
            }
        }
        return -1;
    }
};

 

이러면 시간복잡도 O(N) 일 것이다. 해시는 O(1)이고, 반복문을 각각 따로 두 번 돌리니까 말이다.

 

개선코드 및 회고

결과를 보니 통과는 했지만 14ms로 꽤 중간에 분포한다. 

상위에 있는 코드를 보니 해시맵을 안쓰고 그냥 벡터로 숫자 카운트 해서 동일하게 두 번 반복문 돌려서 찾고 있다.

동일한데 벡터로 써서 더 시간이 빠르다는 것이다.

해시는 해시 충돌이 발생할 경우 O(N)이 될 수도 있고,

벡터가 메모리 할당이 한 번에 이뤄져서 인덱싱이 빠르기 때문에 더욱 빠른 결과를 가져올 수 있게 되는 것 같다.

원소수를 카운트하면 해시를 쓴다라는 생가에 너무 갇혀 있었던 것 같다.

특히나 글자수가 고정되어 있는 상태라면 벡터를 고려하자!

class Solution {
public:
    int firstUniqChar(string s) {
        vector<int> v(27,0);
        for (int i=0;i<s.size();++i){
            v[s[i]-'a']++;
        }
        for (int i=0;i<s.size();++i){
            if (v[s[i]-'a']==1){
                return i;
            }
        }
        return -1;
    }
};