본문 바로가기
Computer Science/Datastructure & Algorithm

Q. 문자열을 뒤집는 모든 방법

by sohyunwriter 2021. 2. 1.

Q. 문자열 뒤집는 방법을 아는 대로 말하면?

 

이러한 질문을 면접 때 받은 적이 있다.

정말 아는 대로 말하면 되는데, 

당시에 투포인터 solution을 말하지 못했다.

 

java, python 등 대부분 문자열을 뒤집는 함수가 내장되어 있는데, 

안에를 뜯어보면 투포인터로 구현되어 있다.

 

그리고 나중에 다른 지원자들과 복기를 했을 때, 

투포인터 solution을 말한 사람이 거의 없었다.

또, 지원하는 언어의 특징에 맞게 대답한 사람도 거의 없었다.

 

 

-출제 의도

1) 간단한 알고리즘조차 잘 구현 못하는 지원자는 거르고 싶다

2) 지원하는 언어에 어울리는 해결방식으로 이 간단한 문제를 해결하는지 보고 싶다.

 

 

-고득점 비결

1) inplace로 뒤집을 수 있는 방법 말하기(=투포인터 이용 solution)

2) 지원하는 언어에 어울리는 해결 방식 말하기

 

 

A.

1) (for문 이용) for문을 '문자열길이-1'부터 시작해 '0'까지 돌면서 반환한다

 

 

2) (투포인터 이용) 시작과 끝을 투포인터로 잡고 swap 하고, 투포인터를 한 칸씩 이동시킨 후 다시 또 swap하는 과정을 반복한다.

 

리턴 없이 리스트 내부를 직접 조작하는 방식이어서 space complexity는 O(1)

time complexity는 O(N)

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        left, right = 0, len(s)-1
        while left < right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1

 

 

3) 언어별 내장함수 이용

-python에서 reverse() 함수 이용

-python에서 [::-1] 이용

-JAVA에서 StringBuffer 클래스의 reverse() 함수 이용

 

 

 

-참고문헌

더보기
728x90

댓글0