Level 1. 가장 가까운 같은 글자

Level 1. 가장 가까운 같은 글자

 

 

단순한 방법이라면 이중 for문을 돌면서 자신보다 앞에 있는 같은 글자를 찾을 수도 있지만 O(n²) 시간이 소요되며 비효율적이다.

 

차례대로 순회하면서 각 문자가 가장 마지막에 등장한 위치를 저장하고 확인할 수 있다면 O(n) 시간이 소요된다.

 

map을 활용해 마지막 등장 위치를 저장하고 확인하여 해결했다.

 

map에서 키의 존재 여부를 확인하기 위해 map.find()나 map.count()를 쓰는 경우도 있는데, map의 구현 스펙을 참고하면 키가 존재하지 않는 경우를 0이나 NULL로 확인하는 방법도 안전하다고 알려져 있다.

 

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

vector<int> solution(string s)
{
    size_t N = s.length();
    vector<int> answer(N);
    unordered_map<char, int> umap;

    for (int i = 0; i < N; ++i)
    {
        if (umap[s[i]] == 0)
            answer[i] = -1;
        else
            answer[i] = i - umap[s[i]] + 1;

        umap[s[i]] = i + 1;
    }

    return answer;
}