[Hackerrank] Super Reduced String

문제 설명

문자열의 소문자 문자들로 이루어진 문자열 sss가 주어집니다. 다음과 같은 작업을 반복하여 문자열을 줄이는 과정을 수행하세요:

• 한 번의 작업에서, 서로 인접한 두 문자가 같으면 그 둘을 삭제합니다.

가능한 한 많은 문자를 삭제한 후, 결과 문자열을 반환하세요. 만약 최종 문자열이 비어있다면 "Empty String"을 반환합니다.

---

예제

예제 입력 1

입력:
s = "aab"

설명:

• 첫 번째 작업에서 인접한 문자 'a' 두 개를 삭제하면 문자열은 "b"가 됩니다.
• 결과: "b"

출력:
"b"

예제 입력 2

입력:
s = "abba"

설명:

• 첫 번째 작업에서 인접한 문자 'b' 두 개를 삭제하면 문자열은 "aa"가 됩니다.
• 두 번째 작업에서 인접한 문자 'a' 두 개를 삭제하면 문자열은 비어버립니다.
• 결과: "Empty String"

출력:
"Empty String"

---

함수 설명

함수 superReducedString을 완성하세요.
이 함수는 다음과 같은 매개변수를 받습니다:

• string s: 줄여야 할 문자열

반환값:

• string: 결과 문자열 또는 비어있다면 "Empty String" 반환

---

입력 형식

• 하나의 문자열 sss가 입력으로 주어집니다.

이 문제는 인접한 동일한 문자 쌍을 반복적으로 없애고 남은 문자열을 반환하는 문제이다. 

문자열을 줄이기 위해서 문자열을 list로 선언한다. 그리고 is_change 변수를 false로 선언하고, 문자열의 0부터 전체길이 - 1까지 탐색을 한다. 그래서 만약 해당 문자와 그 다음 문자가 동일하면, 두 문자를 없애고, is_change 변수를 True로 바꾸어준다. 변경이 발생한다면 처음부터 문자열을 다시 탐색해야하므로 루프를 처음부터 다시 반복한다. 만약 is_change 변수가 false라면 더 이상 바뀔게 없다는 뜻이므로, break해서 해당 문자를 return해준다. 만약 문자열이 비어있다면 empty string을 return해준다. 해당 코드는 다음과 같다.

def superReducedString(s):
    s_list = list(s)
    while True:
        is_change = False
        for i in range(0, len(s_list) - 1):
            if s_list[i] == s_list[i + 1]:
                s_list.pop(i + 1)
                s_list.pop(i)
                is_change = True
                break
        if is_change:
            continue
        else:
            break
    if s_list == []:
        return "Empty String"
    else:
        return "".join(s_list)

해당 코드는 O(n^2)의 시간 복잡도를 가진다. 왜냐하면 문자열을 pop하고 다시 탐색하기 때문이다. 문제의 조건이 어렵지 않았기에 문제를 통과했지만, 스택을 이용하여 O(n)의 시간 복잡도를 가지게 코드를 수정해보았다. 스택을 이용하여 문자열을 처음부터 끝까지 스택에 넣으면서, 스택의 마지막 요소와 현재 문자가 동일하면 2개의 문자열을 제거하는 방식을 이용하였다. 해당 코드는 다음과 같다.

def superReducedString(s):
    stack = []
    for char in s:
        if stack and stack[-1] == char:
            stack.pop()
        else:
            stack.append(char)
    
    return ''.join(stack) if stack else "Empty String"