< 프로그래머스 C++ > 가장 가까운 같은 글자

문자열 s가 주어졌을 때, s의 각 위치마다 자신보다 앞에 나왔으면서 자신과 가장 가까운 곳에 있는 같은 글자가 어디 있는지 알아내는 문제이다.

 

s = "banana" result = [-1, -1, -1, 2, 2, 2]

s = "foobar" result = [-1, -1, 1, -1, -1, -1]

---

문제 해석

각 글자에서 다음 두 가지를 확인하면 된다.

 

1. 자신 이전 구간에 같은 글자가 있는가?
2. 있다면 가까운 위치까지의 거리는?

여기서 핵심은 "가장 가까운" 이라는 조건이다. 앞에 글자가 있어도 자기 자신과 제일 가까운 것 하나만 찾으면 된다.

 

이를 구하기 위해서 역순 탐색 기법을 사용했다.

---

문제 풀이

#include <string>
#include <vector>
using namespace std;

vector<int> solution(string s) {
    vector<int> answer;
    
    for (int i = 0; i < s.size(); i++) {
        if (i == 0) {
            answer.push_back(-1);
            continue;
        }
        
        size_t pos = s.rfind(s[i], i - 1);
        
        if (pos == string::npos) {
            answer.push_back(-1);
        } else {
            answer.push_back(i - pos);
        }
    }
    
    return answer;
}

 

핵심 포인트

1. rfind()

rfind는 문자열을 뒤에서부터 검색해서 일치하는 위치를 반환하는 함수이다.

문자열.rfind(찾을문자, 시작위치);

• 찾을 문자 - 검색할 문자(또는 부분 문자열)
• 시작 위치 - 검색을 시작할 인덱스 값. 여기서부터 앞쪽으로 검색을 이어나간다.

이번 문제에서는 s.rfind(s[i], i - 1) 처럼 사용했다.

"i번째 글자와 같은 문자를 i-1 위치부터 앞쪽으로 검색"

이라는 뜻이다.

 

2. string::npos

rfind나 find함수는 결과를 찾지 못했을 때, string::npos라는 값을 반환한다.

size_t pos = s.rfind(s[i], i - 1);

if (pos == string::npos) {
    // 찾지 못한 경우
}

다른 함수의 종류와는 좀 다르게 string의 find는 이러한 값을 내보낸다.

함수 종류	못 찾을 때 반환값
Vector의 find	end()
String의 find	string::npos
map의 find	end()

 

3. 거리 계산

answer.push_back(i - pos);

가장 가까운 같은 글자의 위치를 찾았다면, 현재 위치 i에서 그 위치 pos값을 빼면 거리가 나온다.

 

banana의 마지막 a를 예로 들면

 

s.rfind('a', 4) > 4번 인덱스부터 거꾸로 검색 > 인덱스 3에서 a 발견

5 - 3 = 2

 

4. 첫 글자 예외 처리

첫 글자는 비교할 글자가 없으므로 바로 -1을 입력해주면 된다.

입력이 완료된 후에 continue로 다음 반복문을 진행해주는 것도 잊지 않는다.

if (i == 0) {
    answer.push_back(-1);
    continue;
}

 

---

다른 풀이 - map활용(코드리뷰)

#include <string>
#include <vector>
#include <map>

using namespace std;

vector<int> solution(string s)
{
    map<char, int> mp;
    vector<int> answer;
    for (int i = 0; i < s.size(); ++i)
    {
        if (mp.find(s[i]) != mp.end()) answer.push_back(i - mp[s[i]]);
        else answer.push_back(-1);
        mp[s[i]] = i;
    }
    return answer;
}

 

rfind는 매번 앞쪽 전체를 검색하기 때문에 시간 복잡도가 O(N^2)에 가깝다. N이 10000정도는 큰 문제는 없지만, 더 효율적인 방법으로 마지막 등장 위치를 기록하는 방식이 있다.

동작 원리

• mp[c]에 문제 c가 마지막에 등장한 위치를 저장
• 새 글자를 만나면 맵에서 즉시 조회
• 처리 후 자신의 위치로 갱신

이 방식의 장점은 이전 위치를 다시 검색할 필요가 없다는 것이다. rfind처럼 매번 앞쪾을 거꾸로 훑지 않고, 맵에서 한 번에 꺼낸다.

 

map의 find패턴

if (mp.find(s[i]) != mp.end())

맵에 키가 있다면 거리를 계산하는 조건문이다.

 

이렇게 

이전에 본 무언가의 위치를 기억해야 할 때

는 맵 계열 자료구조를 떠올리면 좋다.