문제 설명
소문자로만 이루어진 문자열 s가 주어졌을 때, s에 포함된 문자들을 조합하여 만들 수 있는 "pizza" 문자열의 개수를 구하는 것이 목표입니다. 문자들은 임의의 순서로 재배치할 수 있지만, 각 문자는 한 번만 사용할 수 있다는 점에 유의해야 합니다.
예를 들어 입력이 "ihzapezlzzilaop"라면, "pizza" 두 개를 만들 수 있을 만큼의 문자가 충분히 포함되어 있으므로 출력은 2가 됩니다.
접근 방법
"pizza"는 총 5글자이며, 각 알파벳은 다음과 같이 필요합니다.
- 'p': 1개
- 'i': 1개
- 'z': 2개
- 'a': 1개
따라서 해결 절차는 다음과 같습니다.
- p_freq := s에서 'p'의 빈도수
- i_freq := s에서 'i'의 빈도수
- z_freq := s에서 'z'의 빈도수
- a_freq := s에서 'a'의 빈도수
- (p_freq, i_freq, z_freq // 2, a_freq) 중 최솟값 반환
여기서 'z'의 빈도수를 2로 나누는(z_freq // 2) 이유는, "pizza" 하나를 완성할 때마다 'z'가 두 개씩 소모되기 때문입니다. 네 가지 값 중 가장 작은 값이 실제로 만들 수 있는 "pizza"의 최대 개수가 됩니다.
구현 예제
class Solution:
def solve(self, s):
p_freq = s.count('p')
i_freq = s.count('i')
z_freq = s.count('z')
a_freq = s.count('a')
return min(p_freq, i_freq, z_freq // 2, a_freq)
ob = Solution()
print(ob.solve("ihzapezlzzilaop"))
입력
"ihzapezlzzilaop"
출력
2
복잡도 분석
s.count() 메서드는 문자열을 한 번씩 순회하므로 시간 복잡도는 O(n)이며, 추가적인 자료구조를 사용하지 않으므로 공간 복잡도는 O(1)입니다. 파이썬의 내장 count() 함수와 min() 함수를 활용하면 매우 간결하게 문제를 해결할 수 있습니다.