[Python algorithm interview] string_2 문자열 뒤집기

 

파이썬 알고리즘 인터뷰의 2020ver.을 리뷰하고 있습니다.

 

2. 문자열 뒤집기

 

이번에는 매우 간단한 문항입니다. 저자에 의하면 투 포인터(Two pointer)라는 방식과

reverse()를 사용하는 방식으로 풀이가 가능합니다.

 

 

🎈문제

 

문자열을 뒤집는 함수를 작성하라. 입력값은 문자 배열이며, 리턴 없이 리스트 내부를 직접 조작하라.

 

🔑입력 예제

 

["h", "e", "l", "l", "o"]

["o", "l", "l", "e", "h"]

 

두번째

 

['H', 'a' , 'n', 'n', 'a', 'h']

['h', 'a' , 'n', 'n', 'a', 'H']

 

🛴 풀이법. ep1 two pointer

 

def se1(s:list[str]):
    left, right = 0, len(s)-1
    while left < right:
        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1
    print(s)

 

two pointer란?

투 포인터는 왼쪽 포인터와 오른쪽 포인터의 합이 target보다 크다면 오른쪽 포인터를 왼쪽으로,

작다면 왼쪽 포인터를 오른쪽으로 옮기면서 값을 조정하는 방식입니다.

 

다시, 시작점과 끝점(=왼쪽 포인와 오른쪽 포인터) 두 지점을 기준으로 하는 문제풀이 전략을 의미합니다.

2개의 포인터가 좌우로 자유롭게 움직일 수 있기 때문에 'two' pointer가 됬다고 합니다.

 

배열 [ 1, 2, 3, 4, 5]의 경우 투포인터가 도입된 예시

 

Hannah를 활용했습니다.

특별하게도 이 문자열도 지난번 글에서 봤던 펠린드럼인 점을 확인할 수 있네요.

 

 

left 는 1씩 증가하고, right는 1씩 감소(-1씩 증가)하여 이를 문자 인덱스에

넣어서 서로의 인덱스가 교차되도록 만듭니다.

 

        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1

 

이 과정은 left가 right보다 커질 경우 종료됩니다. while문 사용.

 

    while left < right:
        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1

 

전체적으로 보겠습니다.

 

def se1(s:list[str]):
    left, right = 0, len(s)-1
    while left < right:
        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1
    print(s)

---

 

 

👇 reverse()를 이용한 사례

 

# 속도가 약간 더 줄어든 풀이
def se2(s:list[str]):
    s.reverse()
    print(s)

 

이렇게 되면 머리를 써서 알고리즘 풀이를 하는 이유가 상당부분 사라지겠죠?

 

reverse()는 입력값이 리스트로 제공되면 뒤집어 줍니다.

저자에 의하면 two pointer를 이용해서 swap했을때 보다 reverse를 사용했을 때

8밀리초 정도가 줄어든다고 서술하고 있습니다.

 

 

🧭 시간 비교

def se1(s:list[str]):
    start = time.time()
    left, right = 0, len(s)-1
    while left < right:
        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1
    print(s)
    end = time.time()
    print(f'{end - start:.8f}')

se1(['H', 'a' , 'n', 'n', 'a', 'h'])

['h', 'a', 'n', 'n', 'a', 'H']
0.00100136

 

첫번째 방법 : 0.00100136초

 

def se2(s:list[str]):
    start = time.time()
    s.reverse()
    print(s)
    end = time.time()
    print(f'{end - start:.10f}')

se2(['H', 'a' , 'n', 'n', 'a', 'h'])

['h', 'a', 'n', 'n', 'a', 'H']
0.0010008812

 

두번째 방법 : 0.0010008812초

 

 

정말 미세하게 달라지네요.

 

풀이 끝.