[2025.01.20] 가장 가까운 같은 글자

문제 설명

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

• b는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
• a는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
• n은 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
• a는 자신보다 두 칸 앞에 a가 있습니다. 이는 2로 표현합니다.
• n도 자신보다 두 칸 앞에 a가 있습니다. 이는 2로 표현합니다.
• a는 자신보다 두 칸, 네 칸 앞에 a가 있습니다. 이 중 가까운 것은 두 칸 앞이고, 이는 2로 표현합니다.

따라서 최종 결과물은 [-1, -1, -1, 2, 2, 2]가 됩니다.

문자열 s이 주어질 때, 위와 같이 정의된 연산을 수행하는 함수 solution을 완성해주세요.

 

 

제한사항

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

 

 

입출력 예

s			result	설명
"banana"			[-1, -1, -1, 2 ,2, 2]	지문과 같습니다.
"foobar"			[-1, -1, 1, -1, -1, -1]	설명 생략

 

 

문제 풀이

풀이 언어 : C++

#include <string>
#include <vector>

using namespace std;

vector<int> solution(string s) {
    vector<int> answer;
    int ans;
    
    for(int i=0; i<s.length(); i++)
    {
        ans=-1; // 정답 -1로 초기화
        for(int j=i-1; j>=0; j--)
        {
            // 가장 첫 글자가 아니고 두 글자가 같을 때
            if(j!=-1&&s[i]==s[j])
            {
                ans=i-j; // 정답 업데이트
                break; // 반복문 나가기
            }
        }
        // 첫 글자였거나 같은 글자가 없었으면 -1
        // 같은 글자가 있었으면 몇 칸 앞에 있는지
        answer.push_back(ans);
    }
    return answer;
}

 

 

for문을 이용해서 s의 한글자 한글자씩 살펴보게 한다. 그리고 살펴보는 글자 앞으로 차례로 같은 글자가 없는지 확인하면서 같은 글자가 있다면 살펴보고 있는 글자에서 몇 글자 떨어져 있는지 저장한다. 살펴보는 글자가 맨 첫 글자이거나 다 돌아봤는데도 같은 글자가 없다면 -1을 저장한다.

 

즉 for문은 2개가 필요하다. 0번째부터 s를 끝까지 살펴볼 for문과 첫 for문에서 탐색중인 글자부터 모든 앞 글자들 중 같은 글자가 있는지 탐색할 for문이다. 먼저 정답을 저장할 int형 변수 ans을 선언한다. 그리고 바깥 for문이 시작하는 순간 -1로 초기화 한다.

 

그리고 본격적으로 같은 글자가 있는지 탐색을 시작한다. 안쪽 반복문은 i-1부터 시작하여 0까지 반복한다. i번째 글자보다 하나 앞 글자부터 맨 앞글자까지 확인하겠다는 뜻이다. 첫 글자는 앞에 글자가 없기 때문에 s[-1]에 접근하지 않도록 미리 확인하고 제외해주어야 한다. 따라서 if문을 이용해 첫 글자가 아니라는 j!=-1 조건을 추가한다. 그리고 글자가 같은지 확인하기 위해 s[i]와 s[j]를 비교해준다. 같은 글자가 나온다면 ans를 i-j로 초기화 해주고 반복문을 중단한다. 만약 중단하지 않는다면 가장 멀리 있는 같은 글자를 찾게 되므로 주의한다.

 

반복문이 끝나면 answer에 ans를 저장한다. 결과적으로 첫 글자였거나 같은 글자가 없으면 -1이 저장되고 같은 글자가 있었다면 가장 가까운 곳 몇 번째에 같은 글자가 있는지 저장되게 된다.

 

 

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/142086

프로그래머스