[Baekjoon] 6996번 애너그램

https://www.acmicpc.net/problem/6996

 

설명 :

두 String이 주어지고, 서로 anagram 인지를 판별하는 문제이다.

글자의 순서만 뒤바뀌었기 때문에 문자열의 길이와 각 글자의 등장 횟수는 일치한다는 사실을 이용하여 풀면 된다.

먼저 문자열의 길이가 다르면 anagram 이 아니다.

각 글자의 등장 횟수가 같기 때문에 두 문자열을 정렬시킨 후 같은지 보면 되는데 이 방법은 쉽게 풀 수 있지만 O(nlogn)의 시간이 걸린다.

더 나은 방법으로, 배열 하나를 이용하면 된다.

각 글자마다 배열의 위치를 정해준 다음(ASCII 코드의 경우 각 글자가 숫자 하나와 매칭되기 때문에 256 만큼의 길이를 갖는 배열 하나만으로 모든 글자가 매칭된다.)

for문으로 첫번째 문자열을 순회한다.

글자가 등장 할 때마다 각 배열의 위치에 +1 값을 해준다.

for문으로 두번째 문자열을 순회할 때는 글자가 등장 할 때마다 각 배열의 위치에 -1 값을 해준다.

모든 배열의 값이 0이라면 똑같은 횟수만큼 글자가 등장했다는 의미이므로 anagram 이 된다.

배열의 길이만큼 총 3번을 돌기 때문에 3n, 즉 O(n) 만큼의 시간이 걸린다.

ASCII 가 아니고 유니코드라거나 하는 이유에서 배열을 사용하기 껄끄럽다면,

HashMap 를 사용하여도 좋겠다.

다만 Hash 는 (만에 하나) 충돌이 일어날 가능성이 있다는 사실을 염두해두어야 한다.

 

case = int(input())

for i in range(case):

    y = True
    str = input().split(" ")

    if len(str[0])!=len(str[1]):
        y = False
    else:
        l = [0]*26

        for c in str[0]:
            l[ord(c)-ord('a')]+=1
        for c in str[1]:
            l[ord(c)-ord('a')]-=1
        for n in l:
            if n!=0:
                y = False
                break

    print(str[0],"&",str[1],"are ", end="")
    if not y:
        print("NOT ", end="")
    print("anagrams.")

 

코드 : http://boj.kr/167e5d069f954d8ca726a66ce30a52a4