문제 설명
"a"와 "b"로만 이루어진 문자열 s가 있다고 가정해 보겠습니다. 이때 "a"는 그대로 "a"로 남아 있거나 "b"로 바꿀 수 있지만, "b"는 어떤 경우에도 변경할 수 없습니다. 우리의 목표는 이러한 규칙을 적용해 만들 수 있는 고유한 문자열의 총 개수를 구하는 것입니다.
예를 들어 입력이 s = "baab"라고 한다면, 만들 수 있는 문자열은 ["baab", "babb", "bbab", "bbbb"]의 네 가지이므로 출력은 4가 됩니다.
해결 접근 방법
이 문제의 핵심은 간단한 조합론적 사고에 있습니다. 각각의 "a"는 독립적으로 두 가지 선택지를 가집니다. 즉, "그대로 a로 남기거나 b로 바꾸는 것"입니다. 반면 "b"는 선택지가 없으므로 결과에 영향을 주지 않습니다.
따라서 다음과 같은 단계로 문제를 해결할 수 있습니다.
- counts := 문자열 s에 포함된 'a'의 개수
- 2^counts 값을 반환
'a'가 n개 있다면 각 자리마다 2가지 선택이 가능하므로, 전체 경우의 수는 2^n이 됩니다. 예를 들어 "baab"에는 'a'가 2개 있으므로 2² = 4개의 문자열을 만들 수 있습니다.
구현 예제
아래 코드를 통해 더 잘 이해해 보겠습니다.
class Solution:
def solve(self, s):
counts = s.count('a')
total = 2**(counts)
return total
ob = Solution()
print(ob.solve("baab"))
입력
"baab"
출력
4
복잡도 분석
이 풀이의 시간 복잡도는 문자열을 한 번 순회하여 'a'의 개수를 세므로 O(n)이며, 공간 복잡도는 추가 저장 공간 없이 상수만 사용하므로 O(1)입니다. 매우 효율적인 해결책이라 할 수 있습니다.