•
•
문제 설명 : | 구분자로 s 문자열의 쌍을 구분한다. 이때 쌍에 포함되지 않은 문자열들중에서 * 의 갯수를 구한다.
•
풀이 방법
◦
문제가 조금 헷갈릴 수 있다. 여기서 특정 쌍에 사용된 | 문자는 다른 쌍에서 사용되지 않는다는 점을 알면, 조금 쉬워진다.
◦
| 으로 쌍을 반드시 만들어야하기 때문에, | 의 갯수는 s 내부에서 반드시 짝수개이다.
◦
즉, a|bc|d*|ef| 값이 있다면 |bc| 와 |ef| 가 쌍이며 a 와 d* 는 쌍이 아니다.
◦
이미 |bc| 와 |ef| 에서 | 를 사용했기 때문에, d* 앞뒤에 있는 | 는 사용할 수 없다.
◦
결론적으로, | 구분자로 split 을 진행한 리스트의 짝수(0포함) 인덱스에는 쌍이 아닌 문자열이 존재한다.
◦
만약 | 로 시작하고 끝나는 s 문자열이라고해도, | split 사용 시에도 빈 문자열이 첫번째 요소를 채우기 때문에 카운팅에는 문제가 없다.
•
시간복잡도 :
•
성공 코드
# O(N + N + N + N + N) -> O(N)
class Solution:
def countAsterisks(self, s: str) -> int:
# s.split -> 구분자를 사용한 데이터 분리 -> O(N)
# [::2] -> 순회는 s.split()으로 반환된 리스트 길이 만큼, 실제 접근은 그 길이의 절반 -> O(N)
# for문 순회 -> O(N)
# '|' 로 구분된 각 문자열의 '*' 갯수 확인 -> O(N)
# '*' 갯수가 저장된 리스트의 합계 계산 -> O(N)
return sum([exclude.count('*') for exclude in s.split('|')[::2]])
Python
복사