파이썬으로 목표 파서(Goal Parser) 명령어 해석하기

목표 파서(Goal Parser)가 주어진 문자열 명령을 해석하는 상황을 가정해 보겠습니다. 명령 문자열은 다음 세 가지 요소로만 구성됩니다.

알파벳 "G"
여는 괄호와 닫는 괄호 "()"
그리고/또는 "(al)" (순서는 임의)

목표 파서는 "G"를 문자열 "G"로, "()"를 "o"로, "(al)"을 "al"로 해석합니다. 해석된 결과들은 원래 등장한 순서대로 이어 붙여집니다. 따라서 명령 문자열이 주어졌을 때, 목표 파서가 해석한 최종 문자열을 구하는 것이 이 문제의 목표입니다.

예를 들어 입력이 command = "G()()()(al)(al)"이라면, "G"는 그대로 "G", "()" 세 개는 "ooo", "(al)" 두 개는 "alal"로 해석되어 최종 출력은 Goooalal이 됩니다.

문제 해결 접근 방법

이 문제는 문자열을 한 글자씩 순회하며 규칙에 맞게 변환하는 방식으로 해결할 수 있습니다. 단계별로 살펴보겠습니다.

결과를 저장할 빈 문자열 s를 준비합니다.
인덱스 i를 0부터 명령 문자열 길이 - 1까지 반복하면서 다음을 수행합니다.
- command[i]가 "("도 ")"도 아니라면, 해당 문자를 s에 이어 붙입니다.
- command[i]가 "("이고 바로 다음 문자 command[i+1]이 ")"라면(단, i+1 < len(command)), s에 'o'를 이어 붙입니다.
- command[i]가 "(" 또는 ")"라면 현재 문자는 이미 처리되었으므로 다음 반복으로 넘어갑니다.
반복이 끝나면 s를 반환합니다.

파이썬 구현 예제

위 알고리즘을 파이썬 코드로 구현하면 다음과 같습니다.

def solve(command):
    s = ""
    for i in range(len(command)):
        if command[i] != "(" and command[i] != ")":
            s += command[i]
        if command[i] == "(" and i + 1 < len(command) and command[i + 1] == ")":
            s += 'o'
        if command[i] == "(":
            continue
        if command[i] == ")":
            continue
    return s

command = "G()()()(al)(al)"
print(solve(command))

입력

"G()()()(al)(al)"

출력

Goooalal

더 간단한 대안: replace() 활용하기

파이썬의 내장 메서드 replace()를 사용하면 훨씬 간결하게 해결할 수도 있습니다. "()"를 먼저 "o"로 바꾸고, 남은 "(al)"을 "al"로 바꾸면 됩니다. 주의할 점은 "(al)"을 먼저 치환하면 안 되고, "()" 치환이 "(al)" 패턴에 영향을 주지 않으므로 순서는 사실상 자유롭지만 일반적으로 아래와 같이 작성합니다.

def solve(command):
    return command.replace("()", "o").replace("(al)", "al")

command = "G()()()(al)(al)"
print(solve(command))  # Goooalal

복잡도 분석

시간 복잡도: O(n) — 문자열을 한 번만 순회하면 되므로 명령 문자열의 길이에 비례합니다.
공간 복잡도: O(n) — 해석된 결과를 저장할 새로운 문자열이 필요합니다.

두 방식 모두 선형 시간에 동작하지만, 실무에서는 replace()를 활용한 방법이 코드가 짧고 가독성이 뛰어나 더 권장됩니다. 반면 문자 하나씩 처리하는 방식은 파서의 동작 원리를 학습하는 데 유용합니다.