Python으로 멈춘 키보드 키 문제 해결하기: 입력된 문자열이 목표 문자열인지 확인하는 프로그램

두 개의 문자열 s와 t가 있다고 가정해 봅시다. 우리는 t를 만들고 싶지만, 키보드에 일부 키가 눌린 상태로 고착되어 있어서 특정 문자가 한 번 이상 반복해서 입력될 수 있는 상황입니다. 이때 실제로 입력된 문자열 s가 원래 의도했던 문자열 t를 작성하려던 것일 수 있는지 확인해야 합니다.

예를 들어, 입력이 s = "appppleee", t = "apple"이라면 출력 결과는 True가 됩니다. 'p'와 'e'가 여러 번 반복되었더라도 멈춘 키 때문에 발생한 것으로 볼 수 있기 때문입니다.

해결 접근 방법

이 문제를 해결하기 위해 다음 단계를 따릅니다:

• 포인터 i := 0, j := 0으로 초기화합니다.
• s_len := 문자열 s의 길이
• t_len := 문자열 t의 길이
• t_last := 빈 문자열로 초기화 (마지막으로 일치한 목표 문자 저장)
• j < t_len인 동안 반복합니다:
  • i가 s_len과 같다면 False를 반환합니다.
• s[i]가 t[j]와 같다면:
  • t_last := t[j]로 갱신
  • i := i + 1, j := j + 1
• 그렇지 않고 s[i]가 t_last와 같다면:
  • i := i + 1 (멈춘 키로 인한 중복 입력 처리)
• 그 외의 경우:
  • False를 반환합니다.

예제 코드

아래 구현 예시를 통해 더 잘 이해해 보겠습니다:

def solve(s, t):
    i = j = 0
    s_len = len(s)
    t_len = len(t)
    t_last = ""
    while j < t_len:
        if i == s_len:
            return False
        if s[i] == t[j]:
            t_last = t[j]
            i += 1
            j += 1
        elif s[i] == t_last:
            i += 1
        else:
            return False
    if i < s_len:
        return all(char == t_last for char in s[i:])
    else:
        return True

s = "appppleee"
t = "apple"
print(solve(s, t))

입력

"appppleee", "apple"

출력

True

코드 설명

이 알고리즘은 두 포인터를 사용하여 시간 복잡도 O(n)으로 문제를 해결합니다. 핵심 아이디어는 다음과 같습니다:

• 문자 일치 시: 두 포인터를 모두 앞으로 이동하고, 마지막으로 일치한 목표 문자를 t_last에 기록합니다.
• 중복 문자 발견 시: 현재 입력 문자가 직전에 일치했던 문자(t_last)와 같다면, 이는 멈춘 키로 인한 반복 입력이므로 입력 포인터만 이동합니다.
• 일치하지 않는 경우: 의도된 문자열과 맞지 않으므로 즉시 False를 반환합니다.
• 마지막 처리: 목표 문자열은 모두 소진되었지만 입력 문자열에 문자가 남아 있다면, 남은 문자들이 모두 마지막 문자와 동일할 때만 True를 반환합니다.