[리트코드 334] 투 포인터(Two Pointers) 를 활용한 문제풀이1

*투 포인터란? 

시작점과 끝점 또는 왼쪽 포인터와 오른쪽 포인터 두 지점을 기준으로 하는 문제 풀이 전략으로 슬라이딩 윈도우(Sliding Window) 와 비슷한 점이 많아 여러 알고리즘 풀이와 관련해 실전적인 풀이 기법이다. (기본적으로 Call by Reference에 대한 이해도가 필요하다.)

 

334. 문자열 뒤집기(Reverse String) 

Example

- 문자열을 뒤집는 함수를 작성하라. 입력값은 문자 배열이다.

Constraints

- 리턴 없이 리스트 내부를 직접 조작 할 것, 시간복잡도 O(1)

Solution

- 리스트 내부를 수정해야함으로 리스트(s)의 내부를 swap 하는 형태로 문자열을 뒤집는다.

코드 샘플

# python
class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        # 양 끝에 포인터를 위치 시킨다.
        l, r = 0, len(s) - 1
        
        # 왼쪽 포인터가 오른쪽 포인터를 넘지 않을때까지 스왑한다.
        while l < r:
            s[l], s[r] = s[r], s[l]  # swap
            l += 1  # 왼쪽 포인터 우로 한칸 이동
            r -= 1  # 오른쪽 포인터 좌로 한칸 이동

 

// kotlin
class Solution {
    fun reverseString(s: CharArray): Unit {
        var l = 0
        var r = s.size - 1

        while (l < r) {
            s[l] = s[r].also { s[r] = s[l] }
            l++
            r--
        }
    }
}

실행 결과

 

참조: 파이썬 알고리즘 인터뷰 https://github.com/onlybooks/algorithm-interview