•
문제 설명 : 2글자의 문자로 이루어진 문자열 목록을 제시하며, 이 문자열 목록 중 같은 문자로 이루어진 쌍의 갯수를 찾는다.
•
풀이 방법
◦
defaultdict 를 사용하여, 문자열의 존재 갯수를 저장한다.
◦
각 문자열을 확인하면서, 현재 word와 쌍 문자열인 뒤집은 word도 함께 카운트한다.
▪
이때 이후 쌍인 문자열이 나오게 된다면, word/뒤집은 word를 key로 사용하는 value값이 2가 될 것 이다.
◦
value가 2 이상인 key를 모두 확인(쌍이 있는 key모두 확인)
▪
갯수를 절반으로 나눠야 쌍의 갯수를 확인할 수 있기 때문에, 2로 나눈다.
•
시간복잡도 :
•
성공 코드
from collections import defaultdict
# O(N + N) -> O(N)
class Solution:
def maximumNumberOfStringPairs(self, words: List[str]) -> int:
# 문자열의 존재 갯수를 저장
info_dict = defaultdict(int)
result = 0
# 각 문자를 순회 -> O(N)
for word in words:
# 현 문자열 갯수 저장
info_dict[word] += 1
# 뒤집은 문자열의 갯수도 저장
if word[0] != word[1]:
info_dict[word[1] + word[0]] += 1
# 갯수를 저장한 dict 순회 -> O(N)
for k, v in info_dict.items():
if v > 1:
result += 1
# 동일 문자로 이루어진 두 문자열은 하나의 갯수(쌍)으로 카운팅하기 때문에, 2로 나누어준다.
return result // 2
Python
복사