[C++] - 가장 가까운 같은 글자

핵심 아이디어

문자를 왼쪽부터 순회하면서 각 문자가 마지막으로 등장한 위치를 저장한다.

현재 위치 i에서 같은 문자가 이전에 나왔으면

 

현재 위치 - 마지막 위치

 

를 저장하고,

처음 나온 문자라면

 

-1

 

을 저장한다.

---

사용한 개념

unordered_map

 

unordered_map<char, int> lastIndex;

 

• Key : 문자
• Value : 마지막으로 등장한 위치
• 빠른 검색 가능 (평균 O(1))

예시

 

lastIndex['a'] = 3;

 

의 의미

 

'a'가 마지막으로 나온 위치는 3

 

---

map vs unordered_map

mapunordered_map

자동 정렬	정렬 안 함
O(log N)	평균 O(1)
트리 구조	해시 테이블

정렬이 필요 없고 빠른 검색만 필요하므로 unordered_map 사용.

---

소문자만 나온다면

 

vector<int> last(26, -1);

 

사용 가능

문자를 배열 인덱스로 변환

 

s[i] - 'a'

 

예시

 

'a' -> 0
'b' -> 1
'c' -> 2

 

unordered_map보다 더 간단하고 빠름.

---

배운 점

• 문자의 이전 위치를 기억해야 하는 문제는 map, unordered_map을 떠올리기
• 문자의 종류가 적고 고정되어 있으면 배열(vector)로 대체 가능
• s[i] - 'a'를 통해 문자를 숫자 인덱스로 변환할 수 있음.