가장 가까운 같은 글자

문제

 

문제 해석

- 길이가 10,000이므로 O(N^2)으로 풀어도 문제가 없겠다 생각
- 해당 문자로부터 가장 앞에 있는 것을 검색하는것이므로 IDX와 IDX -1번째부터를 검색하는 것으로 풀면 되겠다 생각
- 찾지 못한 경우를 생각해야 하므로 bool 변수 생각, 못 찾은 경우 -1로 설정하는 것은 처음 answer에서 -1을 채워놓으면 됨.
- IDX로부터 검색해야 하는 것은 0번 인덱스까지로 설정

 

코드

#include <string>
#include <vector>

using namespace std;

vector<int> solution(string s) {
    vector<int> answer(s.length(), -1);
    
    
    for(int IDX = 0; IDX < s.length(); ++IDX)
    {
        bool bFind = false;
        for(int FindIDX = IDX - 1; FindIDX >= 0; --FindIDX)
        {
            if(s[FindIDX] == s[IDX])
            {
                bFind = true;
                answer[IDX] = IDX - FindIDX;
                break;
            }
        }      
    }
    
    return answer;
}

 

 

다른 사람의 풀이

O(n)으로 풀기 위해서 알파벳에 해당하는 배열을 하나 더 두고 가장 마지막으로 해당 알파벳이 나온 위치를 기록해 두는 방식으로 풀이함. string s의 길이가 극단적으로 길어지면 위의 풀이처럼 하는 것보다는 O(n)으로 할 수 있는 방법인 이 방법을 사용하는 것이 더 옳음.