풀이_LC821.md

〽️ 821. Shortest Distance to a Character

• Date : 2021.12.12(일)
• Time : 30분

Problem

• Given a string s and a character c that occurs in s, return an array of integers answer where answer.length == s.length and answer[i] is the distance from index i to the closest occurrence of character c in s.
• The distance between two indices i and j is abs(i - j), where abs is the absolute value function.

Constraints

• 1 <= s.length <= 10^4
• s[i] and c are lowercase English letters.
• It is guaranteed that c occurs at least once in s.

Example

• Input: s = "loveleetcode", c = "e"
• Output: [3,2,1,0,1,0,0,1,2,2,1,0]
• Explanation:

  The character 'e' appears at indices 3, 5, 6, and 11 (0-indexed).
  The closest occurrence of 'e' for index 0 is at index 3, so the distance is abs(0 - 3) = 3.
  The closest occurrence of 'e' for index 1 is at index 3, so the distance is abs(1 - 3) = 2.
  For index 4, there is a tie between the 'e' at index 3 and the 'e' at index 5, but the distance is still the same: abs(4 - 3) == abs(4 - 5) = 1.
  The closest occurrence of 'e' for index 8 is at index 6, so the distance is abs(8 - 6) = 2.
  

풀이

    def shortestToChar(self, s: str, c: str) -> List[int]:
        locations = list(filter(lambda x: s[x] == c, range(len(s))))
        n = len(locations) - 1
        currentC = 0
        result = []

        for i, char in enumerate(s):
            dist1 = abs(i - locations[currentC])
            if currentC != n:
                dist2 = abs(i - locations[currentC+1])
                if dist1 > dist2:
                    currentC += 1
                    dist1 = dist2
            result.append(dist1)
        return result

: 이 문제는 c에 기준 문자가 하나 주어지고, s에서 가장 가까운 문자 c까지의 거리를 구하는 문제이다. 그래서 먼저 문자 c에 들어온 기준 문자들이 s에 어디에 위치해 있는지 filter를 사용해서 필터링 해서 locations에 저장해주었다. 그리고 currentC는 현재 locations에서 문자 c를 사용하기 위한 인덱스 번호이다. 그리고 s 문자열을 문자, 인덱스 각각 가져오기 위해 enumerate() 를 사용해주었다. 가장 가까운 c와의 거리를 구하기 위해 빼서 dist1에 저장해주었다. 이전 이후 상관없기 때문에 절대값을 표현하기 위해 abs() 함수를 사용해주었다. 만약에 현재 c의 위치가 마지막 c가 아닐때에는 그 다음 c와 더 까운지 검사를 한번 더 해주었다. 그 다음 c와 더 까갑다면 그 다음값으로 변경을 해준다.