파이썬으로 구분자 순서를 유지하며 문자열의 단어만 반전시키는 프로그램

문자열 하나와 구분자(delimiter) 집합이 주어졌을 때, 구분자들의 상대적인 위치와 순서는 그대로 유지한 채 문자열 안의 단어들만 반대 순서로 뒤집는 문제를 생각해 볼 수 있습니다.

예를 들어 입력이 s = "Computer/Network:Internet|tutorialspoint", delims = ["/", ":", "|"] 라면, 출력은 다음과 같아야 합니다.

tutorialspoint/Internet:Network|Computer

해결 접근 방법

이 문제는 파이썬의 itertools.groupby를 활용하면 깔끔하게 해결할 수 있습니다. 전체 알고리즘은 다음과 같습니다.

words: 단어를 저장할 새로운 리스트를 생성합니다.
ans: 결과를 담을 빈 문자열을 초기화합니다.
문자열을 순회하며 구분자가 아닌 문자들로 이루어진 단어만 분리해서 words 배열에 저장합니다.
문자열을 다시 한 번 순회하면서, 현재 문자가 구분자에 해당하면 그대로 ans에 추가합니다.
구분자가 아니라면 words 배열에서 뒤에서부터(역순으로) 단어를 꺼내 ans에 추가합니다.
최종적으로 ans를 반환합니다.

핵심 아이디어는 스택처럼 동작하는 list.pop()을 사용해 단어를 역순으로 꺼내되, 구분자는 원래 자리에 그대로 두는 것입니다.

구현 예제

from itertools import groupby
class Solution:
    def solve(self, sentence, delimiters):
        words = []
        ans = ""

        # 구분자가 아닌 연속된 문자 묶음(단어)만 추출
        for k, g in groupby(sentence, lambda x: x in delimiters):
            if not k:
                words.append("".join(g))

        # 구분자는 그대로 두고, 단어는 역순으로 배치
        for k, g in groupby(sentence, lambda x: x in delimiters):
            if k:
                ans += "".join(g)
            else:
                ans += words.pop()
        return ans

ob = Solution()
s = "Computer/Network:Internet|tutorialspoint"
delims = ["/", ":", "|"]
print(ob.solve(s, delims))

입력

"Computer/Network:Internet|tutorialspoint", ["/", ":", "|"]

출력

tutorialspoint/Internet:Network|Computer

동작 원리 정리

groupby는 인접한 요소들을 키 함수의 반환값 기준으로 묶어주는 함수입니다. 첫 번째 순회에서는 키가 False(구분자 아님)인 그룹, 즉 단어들만 모아 리스트에 쌓고, 두 번째 순회에서는 구분자 그룹은 원본 순서대로 출력하고 단어 그룹은 리스트 끝에서부터 꺼내(pop()) 붙입니다. 이렇게 하면 시간 복잡도 O(n)으로 구분자의 원래 위치를 보존하면서 단어만 반전시킬 수 있습니다.