문자열 S가 주어졌을 때, 영문자가 아닌 문자들은 원래 위치에 그대로 두고 영문자들의 위치만 서로 뒤바꾼 새로운 문자열을 구하는 문제입니다. 예를 들어 입력이 "a-bC-dEf-ghIj"라면 하이픈(-)의 위치는 변하지 않고 영문자만 역순으로 배치되어 "j-Ih-gfE-dCba"가 출력됩니다.
해결 접근 방식
이 문제는 두 포인터(two pointer) 기법으로 효율적으로 해결할 수 있습니다. 앞쪽을 가리키는 index1과 뒤쪽을 가리키는 index2를 사용해 다음 단계대로 진행합니다.
- 문자열 S가 비어 있으면 그대로 반환합니다.
- 결과를 저장할 빈 문자열 str을 준비하고, index1은 0(문자열 시작), index2는 len(S)-1(문자열 끝)로 초기화합니다.
- index1이 문자열 길이보다 작은 동안 아래 조건에 따라 반복합니다.
- index2가 0 이상이고 S[index1]과 S[index2]가 모두 영문자라면 → str에 S[index2]를 추가하고 index2는 1 감소, index1은 1 증가
- S[index1]은 영문자지만 S[index2]가 영문자가 아니라면 → 교환 대상을 찾을 때까지 index2만 1 감소
- S[index1]이 영문자가 아니라면 → 해당 문자를 그대로 str에 추가하고 index1만 1 증가
- 그 외의 경우 → index2를 1 감소시키고 index1을 1 증가
- 반복이 종료되면 완성된 문자열 str을 반환합니다.
구현 예제
아래 파이썬 코드를 통해 해결 과정을 더 쉽게 이해할 수 있습니다.
class Solution:
def reverseOnlyLetters(self, S):
if not S:
return S
str_ = ""
index1 = 0
index2 = len(S) - 1
while index1 < len(S):
if index2 >= 0 and S[index1].isalpha() and S[index2].isalpha():
str_ += S[index2]
index2 -= 1
index1 += 1
elif S[index1].isalpha():
index2 -= 1
elif not S[index1].isalpha():
str_ += S[index1]
index1 += 1
else:
index2 -= 1
index1 += 1
return str_
ob1 = Solution()
print(ob1.reverseOnlyLetters("a-bC-dEf-ghIj"))
실행 결과
입력
"a-bC-dEf-ghIj"
출력
"j-Ih-gfE-dCba"
복잡도 분석
두 포인터가 문자열을 각각 한 번씩 순회하므로 시간 복잡도는 O(n)이며, 결과 문자열을 저장하기 위한 공간 복잡도 역시 O(n)입니다. 참고로 위 코드처럼 str += ... 형태의 문자열 연결을 반복하면 매번 새로운 문자열 객체가 생성되어 성능이 저하될 수 있습니다. 실전에서는 리스트에 문자를 담아두었다가 마지막에 join()으로 합치는 방식이 더 효율적이니 상황에 맞게 선택하시기 바랍니다.