[Python] HackerRank - Anagram

Problem

 

Solving Process

 

일단 든 생각은

절반으로 나눈 후,

알파벳 순으로 정렬을 해서 인덱스마다 다르면 카운트를 세주자! 였는데,

그렇게 하면 동일 알파벳 갯수가 여러개인 경우가 있으니, 불가능했다.

 

그래서 생각해낸 방법은

절반으로 나누어 s1, s2를 만들어서

s1 루프를 돌며

해당 항목이 s2에 있는지 확인하고

s1, s2에 있는 항목을 둘다 제거해주는 방법이다.

하지만,, list로 진행하다보니 time exceeded가 나는 것이어따...

 

그래서 list 보다 시간 복잡도를 줄일 수 있는 deque를 활용하여 풀어주었다!

확실히 remove 시간이 많이 줄은 것 같다. ( list - O(N) , deque - O(1) )

 

+

하지만 역시 고수들의 답은 또 달랐다.

python의 Counter함수를 사용한 것 이었다.

Counter 함수는 해당리스트의 원소의 갯수를 세어 dictionary 형태로 나타낸다.

s1에서 나온 값과 s2에서 나온 값을 빼주면 s2에 없는 s1의 값들만 남게되고

values들을 더해주면 되는 방식이다.

 

Solution

#My Solution
from collections import deque

def anagram(s):
    length = len(s)
    if length % 2:
        return -1
    else:
        s1 = deque(s[:length//2])
        s2 = deque(s[length//2:])
        i = 0
        while i < len(s1):
            if s1[i] in s2:
                s2.remove(s1[i])
                s1.remove(s1[i])
            else:
                i+= 1
    return len(s1)

#Other Solution
from collections import Counter

def anagram2(s):
    if len(s)%2 == 1:
        return -1
    else:
        temp = Counter(s[0:len(s)//2]) - Counter(s[len(s)//2:])
    return sum(temp.values())