[프로그래머스 / C++] 가장 가까운 같은 글자

문제

가장 가까운 같은 글자 : 문제 링크

문제 분석

• 문자열 s가 주어졌을 때, s의 각 위치마다 자신보다 앞에 나왔으면서, 자신과 가장 가까운 곳에 있는 같은 글자가 어디 있는지 알고 싶다. 예를 들어, s = "banana"라고 할 때, 각 글자들을 왼쪽부터 오른쪽으로 읽어 나가면서 다음과 같이 진행할 수 있다.

• b는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없다. 이는 -1로 표현한다.
• a는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없다. 이는 -1로 표현한다.
• n은 처음 나왔기 때문에 자신의 앞에 같은 글자가 없다. 이는 -1로 표현한다.
• a는 자신보다 두 칸 앞에 a가 있다. 이는 2로 표현한다.
• n도 자신보다 두 칸 앞에 n이 있다. 이는 2로 표현한다.
• a는 자신보다 두 칸, 네 칸 앞에 a가 있다. 이 중 가까운 것은 두 칸 앞이고, 이는 2로 표현한다.
• 따라서 최종 결과물은 [-1, -1, -1, 2, 2, 2]가 된다. 문자열 s이 주어질 때, 위와 같이 정의된 연산을 수행하는 함수 solution을 완성

• 제한 사항

  • 1 <= s의 길이 <= 10,000
  • s은 영어 소문자로만 이루어져 있다.

• 문자열이 나온 위치를 저장할 정수형 벡터 alp를 26의 크기로 -1로, 문제의 조건대로 연산 결과를 저장할 정수형 벡터 answer을 초기화. for loop를 통해 문자열 s의 첫번째부터 마지막 원소까지 순환하고, if문을 사용하여 alp내 현재 인덱스의 글자에 해당하는 원소가 -1이라면 처음 나온것을 의미하므로 -1을 answer에 저장. 처음 나온 경우가 아니라면 else문을 사용하여 현재 인덱스에서 alp내에 저장된 이전 위치를 뺀값을 answer에 저장. 이후 alp내 현재 인덱스의 글자에 해당하는 원소의 위치를 최신화. loop 탈출 후, 최종적으로 저장된 answer을 return

풀이

#include <string>
#include <vector>

using namespace std;

vector<int> solution(string s) {
    vector<int> alp(26, -1);
    vector<int> answer;
    
    for(int i = 0; i < s.size(); ++i) {
        if(alp[s[i] - 'a'] == -1) answer.push_back(-1);
        else answer.push_back(i - alp[s[i] - 'a']);
        alp[s[i] - 'a'] = i;
    }
    return answer;
}