파이썬 알고리즘 040 | 아나그램 (딕셔너리 해쉬)

40. Anagram(아나그램 : 구글 인터뷰 문제)

Anagram이란 두 문자열이 알파벳의 나열 순서를 다르지만 그 구성이 일치하면 두 단어는 아
나그램이라고 합니다.
예를 들면 AbaAeCe 와 baeeACA 는 알파벳을 나열 순서는 다르지만 그 구성을 살펴보면
A(2), a(1), b(1), C(1), e(2)로 알파벳과 그 개수가 모두 일치합니다. 즉 어느 한 단어를 재
배열하면 상대편 단어가 될 수 있는 것을 아나그램이라 합니다.
길이가 같은 두 개의 단어가 주어지면 두 단어가 아나그램인지 판별하는 프로그램을 작성하세
요. 아나그램 판별시 대소문자가 구분됩니다.
▣ 입력설명
첫 줄에 첫 번째 단어가 입력되고, 두 번째 줄에 두 번째 단어가 입력됩니다.
단어의 길이는 100을 넘지 않습니다.
▣ 출력설명
두 단어가 아나그램이면 “YES"를 출력하고, 아니면 ”NO"를 출력합니다.
▣ 입력예제 1
AbaAeCe
baeeACA
▣ 출력예제 1
YES

<내 풀이>

• 알파벳(키) : 알파벳 개수(값)으로 설정
• 만약 알파벳(키)가 앞에 있었다면 +1해주며 누적해주기

aa={}
bb={}
a=input()
b=input()

for i in a:
    if i in aa.keys():
        aa[i]+=1
    else : 
        aa[i]=1
        
for i in b:
    if i in bb.keys():
        bb[i]+=1
    else : 
        bb[i]=1

if aa==bb:
    print('YES')
else :
    print('NO')

<풀이>

• (1)

aa={}
bb={}
a=input()
b=input()

for i in a:
    aa[i] = aa.get(i,0)     
for i in b:
    bb[i] = aa.get(i,0)   
for i in aa.keys():
    if i in bb.keys() :
        if aa[i] != bb[i]:  #키는 같은데, 키의 값이 다른 경우
            print('NO')
            break
    else : #키부터 다른 경우
        print('NO')
        break
else : print('YES')
    

• (2) : (1)보다 조금 더 간결, 사전을 하나로 지정해놓고

aa={}
bb={}
a=input()
b=input()
s={}

for i in a:
    s[i]=s.get(i,0)+1    
for i in b:
    s[i]=s.get(i,0)-1 #여기서 증가시켰던 것 감소시키기
for i in a : # a,b가 아나그램이었다면 모든 값은 0이었어야 한다
    if s.get(i) >0:
        print('NO')
        break
    else :
        print('YES')
                

• (3) : 아스키 넘버 사용

aa={}
bb={}
a=input()
b=input()
str1=[0]*52 (대문자, 소문자 총 52자이므로)
str2=[0]*52
for x in a :
    if x.isupper():
        str1[ord(x)-65]+=1 (0~25)
    else :
        str1[ord(x)-71]+=1 (26~51)
for x in b :
    if x.isupper():
        str2[ord(x)-65]+=1
    else :
        str2[ord(x)-71]+=1        
for i in range(52) :
    if str1[i]!=str2[i] :
        print('NO')
        break
else :
    print('YES')

<반성점>

• 아스키 넘버에 대해서 다 까먹었다
  : 대문자 65~90 / 소문자 97~122
  이는 c++이나 자바에서 유용하다고 한다
• 그리고 ord함수로 이를 감싸주면 아스키 넘버가 대신 출력돼서 나오는 것이다

<배운 점>

• 딕셔너리 내장 함수

• 사전이름.get('key',키 없으면 나올 값)
  (사전의 get 내장함수)
  : 키 자리의 키가 존재하면 그 값을 return해주고
  키 자리의 키가 존재하지 않으면 그 옆에 키가 없으면 나올 값을 return
  a.get('A'(키),0)
  =>A라는 키 값이 없으면 0을 return 해준다
  따라서
  a.get('A'(키),0)+1
  이라고 설정해주면 앞에 키가 존재하면 그 키값 +1
  만약 키가 존재하지 않으면 0+1이니깐 1

• 해쉬 관련 용어
  : 키 값으로 이루어진 데이터구조를 의미, 키를 이용해 데이터를 찾는다
  -해쉬(Hash): 임의 값을 고정 길이로 변환하는 것을 의미합니다.
  -해쉬 함수(Hash Function): 특정 연산을 이용하여 키 값을 받아서 value를 가진 공간의 주소로 바꾸어주는 함수를 의미합니다.
  -해쉬 테이블(Hash Table): 해쉬 구조를 사용하는 데이터 구조입니다.
  -해쉬 값(해쉬 주소, Hash Value or Address): Key값을 해쉬 함수에 넣어서 얻은 주소값을 의미합니다. 이 값을 통해 슬롯을 찾아간다.
  -슬롯(Slot): 한 개의 데이터를 저장할 수 있는 공간을 의미합니다. (아래 그림에서는 bucket)

출처: https://davinci-ai.tistory.com/19 [DAVINCI - AI]

-해싱이란 어떤 항목의 탐색 키만을 가지고 바로 항목이 저장되어 있는 배열의 인덱스를 결정하는 기법

<2회독 내 풀이>

aa={}
a=input()
b=input()
for i in a :
    if i in aa.keys():
        aa[i]+=1
    else :
        aa[i]=1
for i in b :
    aa[i]-=1
    
cnt=0
for i in aa.values():
    if i!=0:
        cnt+=1
if cnt==0:
    print('YES')
else :
    print('NO')