821. Shortest Distance to a Character

ee난이도 쉬움이라 가볍게 풀 수 있겠다 싶었는데..

 

python의 리스트 슬라이싱을 헤메서 좀 고생했다. 

역순으로 배열할꺼면 끝값을 지정안해줘도 되는데, 자꾸 습관적으로 지정해서 

왜 안될까 2시간을 고민했다. 

 

문제 자체는 쉽다.

주어진 s 라는 문자열에서 c 문자까지 거리를 측정하는데, 앞뒤중에서 짧은 것을 저장하면 된다. 

 

리스트 슬라이싱과 find로 해결하였다. 

 

    def shortestToChar(self, s: str, c: str) -> List[int]:
        result = []

        for i in range(len(s)):
            left_lst = s[i::-1]
            right_lst = s[i:len(s):1]
            
            lst_pos = left_lst.find(c)
            rst_pos = right_lst.find(c)
            
            if lst_pos >=0 and rst_pos>=0:
                result.append(min(lst_pos, rst_pos))
            elif lst_pos >= 0 and rst_pos == -1:
                result.append(lst_pos)
            elif lst_pos == -1 and rst_pos >= 0:
                result.append(rst_pos)
        return result

 

 

내가 푼 방법보다 좋은 아이디어가 있어 정리차원에서 써둠

 

결국 현재 위치에서 c라는 문자와의 거리를 측정하는 것인데, 

 

정방향으로 진행하면서 내 위치 이전의 c 문자의 위치를 기록해두고, 특정 배열에 넣어둔다

두번째로는 뒤에서 앞으로 오면서 위치를 비교해서 min값을 넣어주면 된다.

 

 

만약 "aaba"이고 "b"라는 문자와의 거리를 생각해보면 

 

i = 0일때, 아직 b의 위치를 못찾았으니 sys.maxSize를 넣고

만약 b를 만나면 b의 위치를 저장하고 다음 문자부터는 b와의 거리를 빼준것을 기록한다. 

 

이제 배열을 뒤로 뒤집어서 b라는 문자의 위치를 기록, 값을 구한다. 

 

    def shortestToChar(self, S: str, C: str):
    	# ex) S = "aaba", C = "b"
        start = -sys.maxsize
        res = []
        for i in range(len(S)):
            if S[i] == C:
                start = i
            res.append(i - start)
        
        # 여기까지 끝나면 res = [999999999, 999999999, 0, 1]이 저장되어 있다. 
        # b의 index가 2이므로 i가 2 이후에는 현재 b의 위치를 가지고 계산.
        
        start = sys.maxsize
        # reversed(range(len(s))를 하면 3,2,1,0 순으로 내려간다....
        
        for i in reversed(range(len(S))):
            if S[i] == C:
                start = i
            res[i] = min(res[i], start - i)
        
        return res