•
문제 링크 : leetcode.com
•
문제 설명 : 제공된 문자열과 문자열 내부의 타겟 문자를 사용하여, 각 요소와 타겟 문자의 최소 거리가 설정된 리스트를 반환
•
풀이 방법
◦
Two Pointer 방식을 사용하여, 타겟 문자를 확인하며 거리를 설정하였다.
◦
중요한점은, 이전에 존재했던 타겟 문자가 더 가까운 거리에 있을 수 있기 때문에 이 부분을 조심해야한다.
•
시간복잡도 :
•
성공 코드
class Solution:
def shortestToChar(self, s: str, c: str) -> List[int]:
left, right = 0, 0
result = []
char_info = []
# 가장 마지막 글자가 c문자가 아닐 수 있다.
while right <= len(s):
# c문자를 만날 때까지 right 커서 이동
while right < len(s) and s[right] != c:
right += 1
# left가 right 커서와 만날 때 까지
while left < right:
# 만약 이미 c문자와 있었다면, 현재 발견한 c문자와 이전 c문자 중 어떤게 더 가까운지 확인
if char_info:
# 현재 커서 위치가 문자열의 범위를 넘어서지 않았다면 비교하여 거리 설정
if right < len(s):
result.append(min(abs(char_info[-1] - left), abs(right - left)))
# 현재 커서 위치가 문자열의 범위를 넘어섰다면, 가장 최근 c문자 위치와 거리 설정
else:
result.append(abs(char_info[-1] - left))
# c문자가 발견된 적이 없다면, 현재 커서와 거리 비교
# c문자는 s내부에서 1번은 반드시 나오기 때문(문제에 명시됨)
else:
result.append(abs(right - left))
# right 방향으로 커서 이동
left += 1
# 문자열 발견 위치 설정
char_info.append(right)
# 다음 c문자를 확인하기 위한 right 커서 이동
right += 1
return result
Python
복사