두 개의 문자열 s와 t가 주어졌을 때, s에서 딱 한 글자를 제거하여 t와 동일하게 만들 수 있는지 확인하는 프로그램을 작성해야 합니다.
예를 들어, 입력이 s = "world", t = "wrld"라면 s에서 'o' 한 글자만 제거하면 "wrld"가 되므로 출력은 True가 됩니다.
문제 해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다:
- 인덱스 변수 i를 0으로 초기화합니다.
- n에 문자열 s의 길이를 저장합니다.
- i < n인 동안 다음을 반복합니다:
- temp에 s의 인덱스 0부터 i-1까지의 부분 문자열과 인덱스 i+1부터 끝까지의 부분 문자열을 이어 붙인 값을 저장합니다. 즉, i번째 문자 하나를 제거한 결과입니다.
- temp가 t와 같다면 True를 반환합니다.
- i를 1 증가시킵니다.
- 모든 위치를 확인한 후에도 일치하지 않으면 False를 반환합니다.
더 나은 이해를 돕기 위해 다음 구현 예제를 살펴보겠습니다.
예제 코드
class Solution: def solve(self, s, t): i = 0 n = len(s) while(i < n): temp = s[:i] + s[i+1:] if temp == t: return True i += 1 return False ob = Solution() s = "world" t = "wrld" print(ob.solve(s, t))
입력
"world", "wrld"
출력
True
코드 설명
위 코드는 문자열 s의 각 위치를 순서대로 순회하면서, 해당 위치의 문자를 제거한 새로운 문자열(temp)을 만드는 방식으로 동작합니다. 파이썬의 슬라이싱 문법인 s[:i]는 인덱스 0부터 i-1까지의 부분 문자열을, s[i+1:]은 인덱스 i+1부터 끝까지의 부분 문자열을 의미합니다. 이 두 부분을 연결하면 i번째 문자가 제거된 문자열이 됩니다.
이렇게 생성한 문자열이 목표 문자열 t와 일치하는지 비교하고, 일치하면 즉시 True를 반환합니다. 끝까지 모든 위치를 확인했는데도 일치하는 경우가 없다면 False를 반환합니다.
이 알고리즘의 시간 복잡도는 O(n²)입니다. 각 위치마다 새로운 문자열을 생성하고 비교하는 데 O(n)의 시간이 소요되며, 총 n개의 위치를 검사하기 때문입니다. 문자열의 길이가 짧은 경우에는 충분히 효율적으로 동작합니다.