프로그래머스 [연습문제 / 가장 가까운 같은 글자](C++) -yes6686- 티스토리

프로그래머스 문제 풀이: 가장 가까운 같은 글자

---

문제 링크: 문제 보기

문제 설명:

문자열 s의 각 문자를 왼쪽에서부터 순서대로 확인하며, 이전에 등장한 같은 문자가 있다면 가장 가까운 위치의 거리(차이)를 저장하고, 없다면 -1을 저장하는 문제입니다.

---

문제 해결 코드

#include <string>
#include <vector>

using namespace std;

int alpha[26]; // 각 문자 마지막 위치 저장

vector<int> solution(string s) {
    vector<int> answer;

    for (int i = 0; i < s.size(); i++) {
        int idx = s[i] - 'a';
        
        if (alpha[idx] == 0) {
            answer.push_back(-1);       // 처음 등장
        } else {
            answer.push_back(i - (alpha[idx] - 1)); // 거리 계산
        }
        alpha[idx] = i + 1; // 현재 위치 저장 (1-based로 저장)
    }

    return answer;
}

---

코드 설명

• 핵심 알고리즘: 각 문자의 마지막 등장 위치를 저장하고, 현재 인덱스와의 차이를 통해 거리를 계산합니다.
• 구현 세부사항:
• alpha 배열은 알파벳마다 마지막으로 등장한 인덱스를 저장합니다. 0이면 처음 등장한 문자입니다.
• 배열은 0으로 초기화되어 있으므로, 실제 위치 저장 시 1을 더해 저장하여 구분합니다.
• 거리 계산은 i - (alpha - 1)로 수행하며, 이후 위치를 갱신합니다.
• 시간 복잡도 분석:
• 문자열 한 번 순회: O(n)
• 총 시간 복잡도: O(n), n은 문자열 길이

---

결과

이 코드는 문자열을 선형으로 순회하며 각 문자에 대해 가장 가까운 이전 등장 위치를 빠르게 계산합니다. 배열을 이용한 인덱스 캐싱을 통해 효율적으로 문제를 해결합니다.

다른 방식으로는 unordered_map을 사용해 가독성을 높일 수도 있으나, 알파벳 소문자만 다룰 경우 배열 방식이 훨씬 빠르고 간결합니다.