문제 개요
문자열 s와 문자 c가 주어졌다고 가정해 봅시다. 이때 c는 반드시 s 안에 존재해야 합니다. 우리가 구해야 할 것은 s와 길이가 같은 리스트로, 각 인덱스 i의 값은 s[i]에서 문자 c까지의 가장 가까운 거리입니다.
예를 들어 입력이 s = "ppqppq", c = "q"라면 출력은 다음과 같습니다.
[2, 1, 0, 1, 1, 0]
각 위치에서 왼쪽 또는 오른쪽에 있는 가장 가까운 'q'까지의 거리를 계산한 결과입니다.
풀이 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
j:= 문자열s의 길이d:= 길이가j이고 모든 값이j - 1인 리스트로 초기화 (최대 가능 거리)x:=s에서 문자c가 처음 등장하는 인덱스i를 0부터j - 1까지 순회하며:s[i]가c와 같고i > x라면, 새로운c의 위치x를i로 갱신하고, 앞쪽 요소들의 거리 값을 더 짧게 줄일 수 있는지 역방향으로 확인하며 업데이트합니다.- 현재 인덱스의 거리 값
d[i]를|x - i|로 설정합니다.
- 완성된 리스트
d를 반환합니다.
구현 예제
아래 파이썬 코드를 통해 더 잘 이해할 수 있습니다.
def solve(s, c):
j = len(s)
d = [j - 1] * j
x = s.index(c)
for i in range(j):
if s[i] == c and i > x:
x = i
ind = 1
while True:
if d[x - ind] > ind:
d[x - ind] = ind
else:
break
ind += 1
d[i] = abs(x - i)
return d
s = "ppqppq"
c = "q"
print(solve(s, c))입력
"ppqppq", "q"
출력
[2, 1, 0, 1, 1, 0]
보너스: 양방향 패스(Bidirectional Pass) 방식
위 알고리즘도 잘 동작하지만, 좀 더 직관적이고 깔끔한 대안으로 두 번의 선형 순회를 사용하는 방법이 있습니다. 먼저 왼쪽에서 오른쪽으로 순회하며 각 위치에서 왼쪽에 있는 가장 가까운 c까지의 거리를 기록하고, 이후 오른쪽에서 왼쪽으로 순회하며 더 짧은 거리가 있으면 갱신하는 방식입니다.
def solve(s, c):
n = len(s)
d = [n] * n
# 왼쪽 -> 오른쪽 순회
prev = float('-inf')
for i in range(n):
if s[i] == c:
prev = i
d[i] = i - prev
# 오른쪽 -> 왼쪽 순회
prev = float('inf')
for i in range(n - 1, -1, -1):
if s[i] == c:
prev = i
d[i] = min(d[i], prev - i)
return d두 방식 모두 시간 복잡도는 O(n)으로 효율적이며, 문자열의 길이가 길어져도 안정적으로 동작합니다.