문자열 a와 하나의 문자 ch가 주어졌을 때, 문자열의 각 문자 위치에서 해당 문자까지의 거리를 계산하여 출력하는 것이 이번 문제의 목표입니다. 문자열의 모든 문자에 대해 거리를 구해야 하므로, 결과 배열의 크기는 원본 문자열의 길이와 동일합니다.
예시
입력 1
a = "tutorialspoint"
ch = 'o'
출력
[3, 2, 1, 0, 1, 2, 3, 3, 2, 1, 0, 1, 2, 3]
설명: 문자열 "tutorialspoint"에는 문자 'o'가 인덱스 3과 인덱스 10에 위치합니다. 따라서 각 인덱스에서 가장 가까운 'o'까지의 거리는 위 배열과 같습니다.
입력 2
a = "programmer"
ch = 'r'
출력
[1, 0, 1, 2, 0, 1, 2, 3, 4, 0]
설명: 문자열 "programmer"에서 'r'은 인덱스 1, 4, 9에 존재하며, 각 위치에서 가장 가까운 'r'까지의 거리는 위 배열과 같습니다.
문제 해결 접근 방식
이 문제를 푸는 가장 직관적인 방법은 무차별 대입(Brute Force) 방식입니다. 먼저 문자열 안에서 목표 문자가 나타나는 모든 위치를 찾아 저장한 뒤, 문자열의 각 위치에 대해 저장된 위치들과의 거리를 비교하여 최솟값을 구합니다.
- 문자열과 문자 ch를 입력으로 받습니다.
- 함수 shortestToChar(string a, char ch)는 문자열과 문자를 입력받아 각 문자로부터 목표 문자까지의 거리를 출력합니다.
- 문자열 a를 한 번 순회하면서 목표 문자가 등장하는 인덱스를 벡터에 저장합니다.
- 다시 문자열을 순회하면서 각 인덱스마다 저장된 위치들과의 절댓값 거리 중 최솟값을 계산합니다.
- 최종 거리 배열을 출력합니다.
이 방법의 시간 복잡도는 문자열 길이를 n, 목표 문자의 등장 횟수를 m이라 할 때 O(n × m)이며, 필요한 추가 공간은 O(n + m)입니다.
C++ 구현 예제
#include<bits/stdc++.h>
using namespace std;
void shortestToChar(string a, char C) {
vector < int > pos, dist;
for (int i = 0; i < a.size(); i++) {
if (a[i] == C)
pos.push_back(i);
}
for (int i = 0; i < a.size(); i++) {
int mn = INT_MAX;
for (int j = 0; j < pos.size(); j++) {
mn = min(mn, abs(pos[j] - i));
}
dist.push_back(mn);
}
for (auto i: dist) {
cout << i << " ";
}
}
int main() {
string a = "tutorialspoint";
char ch {
'o'
};
shortestToChar(a, ch);
}
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
실행 결과
3 2 1 0 1 2 3 3 2 1 0 1 2 3
문자열 "tutorialspoint"에서 문자 'o'는 인덱스 3과 인덱스 10에 존재합니다. 따라서 각 위치에서 앞뒤로 가장 가까운 'o'까지의 거리를 계산하면 [3 2 1 0 1 2 3 3 2 1 0 1 2 3]이 됩니다.