백준 1919번 애너그램 만들기 풀이 python

오늘은 백준 1919번 애너그램 만들기를 풀어볼것이다

이문제는 

 

두 영어 단어가 철자의 순서를 뒤바꾸어 같아질 수 있을 때, 그러한 두 단어를 서로 애너그램 관계에 있다고 한다. 예를 들면 occurs 라는 영어 단어와 succor 는 서로 애너그램 관계에 있는데, occurs의 각 문자들의 순서를 잘 바꾸면 succor이 되기 때문이다.

한 편, dared와 bread는 서로 애너그램 관계에 있지 않다. 하지만 dared에서 맨 앞의 d를 제거하고, bread에서 제일 앞의 b를 제거하면, ared와 read라는 서로 애너그램 관계에 있는 단어가 남게 된다.

두 개의 영어 단어가 주어졌을 때, 두 단어가 서로 애너그램 관계에 있도록 만들기 위해서 제거해야 하는 최소 개수의 문자 수를 구하는 프로그램을 작성하시오. 문자를 제거할 때에는 아무 위치에 있는 문자든지 제거할 수 있다.

입력

첫째 줄과 둘째 줄에 영어 단어가 소문자로 주어진다. 각각의 길이는 1,000자를 넘지 않으며, 적어도 한 글자로 이루어진 단어가 주어진다.

출력

 

첫째 줄에 답을 출력한다.

 

예제 입력 1

 

aabbcc
xxyybb

예제 출력 1

8

 

여기에서 우리가 봐야할건 a와b의 범위가 1000을 넘지 않는다는 것이다 이건 완전 탐색으로 해도 O(1000^2)

 이 최대이기 떄문에 완전탐색으로 해도 상관 없는 문제인것 이다

 

a와 b를 입력받는다 그리고 리스트의 형태로 접근하기위해 리스트로 저장해준다

 

top=0
a=input()
b=input()
a_len=len(a)
b_len=len(b)
astack=['' for i in range(a_len)]
bstack=['' for i in range(b_len)]
for i in range(a_len):
    astack[i]=a[i]
for i in range(b_len):
    bstack[i]=b[i]
astack_l = len(astack)
bstack_l = len(bstack)

 

그후에 중복 문자를 제거한다

 

for i in range(astack_l):
    for j in range(bstack_l):
        if astack[i] == bstack[j]:
            astack[i] = ''
            bstack[j] = ''

 

그후에 빈 문자 만큼 cnt를 1씩 증가시켜준다

 

cnt=0
for i in range(astack_l):
    if astack[i] != '':
        cnt+=1
for i in range(bstack_l):
    if bstack[i] != '':
        cnt+=1

 

완성된 코드:

a=input()
b=input()
a_len=len(a)
b_len=len(b)
astack=['' for i in range(a_len)]
bstack=['' for i in range(b_len)]
for i in range(a_len):
    astack[i]=a[i]
for i in range(b_len):
    bstack[i]=b[i]
astack_l = len(astack)
bstack_l = len(bstack)
for i in range(astack_l):
    for j in range(bstack_l):
        if astack[i] == bstack[j]:
            astack[i] = ''
            bstack[j] = ''

cnt=0
for i in range(astack_l):
    if astack[i] != '':
        cnt+=1
for i in range(bstack_l):
    if bstack[i] != '':
        cnt+=1
print(cnt)