문제 이해하기
두 개의 문자열 s와 t가 주어졌다고 가정해 봅시다. 우리는 s에서 t를 원하는 만큼 여러 번 삭제할 수 있으며, 한 번에 하나의 t만 존재한다고 가정합니다. 목표는 t를 필요한 만큼 반복해서 제거했을 때 s를 완전히 비울 수 있는지 판단하는 것입니다.
예를 들어 s = "pipipinnn", t = "pin"이라면 결과는 True입니다. "pipipinnn"에서 "pin"을 제거하면 "pipinn"이 되고, 다시 "pin"을 제거하면 "pin"이 되며, 마지막으로 한 번 더 제거하면 빈 문자열이 되기 때문입니다.
해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- s의 길이가 0보다 큰 동안 아래 과정을 반복합니다.
- s에서 t가 처음 등장하는 위치(인덱스)를 찾습니다.
- 만약 t를 찾지 못했다면(position이 -1이라면) 반복문을 종료합니다.
- 찾았다면 s에서 t를 한 번 제거한 새로운 문자열로 갱신합니다.
- 반복이 끝난 후 s의 길이가 0이면 true를, 그렇지 않으면 false를 반환합니다.
여기서 핵심은 Python의 두 내장 메서드입니다. find()는 부분 문자열을 찾지 못하면 -1을 반환하고, replace(t, "", 1)는 세 번째 인자 덕분에 첫 번째로 발견된 t 하나만 제거한다는 점입니다.
구현 예제
def solve(s, t):
while len(s) > 0:
position = s.find(t)
if position == -1:
break
s = s.replace(t, "", 1)
return len(s) == 0
s = "pipipinnn"
t = "pin"
print(solve(s, t))입력
"pipipinnn", "pin"
출력
True
동작 방식 정리
코드가 실행되면 먼저 "pipipinnn"에서 "pin"을 찾아 제거해 "pipinn"을 만듭니다. 이어서 "pipinn"에서 "pin"을 제거해 "pin"이 되고, 마지막으로 "pin"을 제거하면 빈 문자열이 됩니다. 이 시점에서 len(s) == 0 조건이 참이 되어 최종적으로 True가 출력됩니다.
시간 복잡도 측면에서 보면, 매 반복마다 find()와 replace()가 문자열 전체를 탐색하므로 최악의 경우 O(n² × m) 수준의 비용이 들 수 있습니다. 입력 크기가 작은 경우에는 충분히 효율적이지만, 매우 긴 문자열을 다룬다면 스택 기반 탐색 등 다른 알고리즘을 고려하는 것이 좋습니다.