[Python] 백준 1919번_애너그램 만들기

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

1919번: 애너그램 만들기

 

• 두 영어 단어가 철자의 순서를 뒤바꾸어 같아질 수 있을 때, 그러한 두 단어를 서로 애너그램 관계에 있다고 함
• 예를 들면 occurs 라는 영어 단어와 succor 는 서로 애너그램 관계에 있는데, occurs의 각 문자들의 순서를 잘 바꾸면 succor이 되기 때문
• 한 편, dared와 bread는 서로 애너그램 관계에 있지 않음
  • 하지만 dared에서 맨 앞의 d를 제거하고, bread에서 제일 앞의 b를 제거하면, ared와 read라는 서로 애너그램 관계에 있는 단어가 남게 됨
• 두 개의 영어 단어가 주어졌을 때, 두 단어가 서로 애너그램 관계에 있도록 만들기 위해서 제거해야 하는 최소 개수의 문자 수 구하기
• 문자를 제거할 때에는 아무 위치에 있는 문자든지 제거 가능

• 입력
  • 첫째 줄과 둘째 줄에 영어 단어가 소문자로 주어짐
  • 각각의 길이는 1,000자를 넘지 않으며, 적어도 한 글자로 이루어진 단어가 주어짐
• 출력
  • 첫째 줄에 답을 출력
• 시간 제한: 2초
• 메모리 제한: 128 MB

 

"""
입출력 예시)

aabbcc
xxyybb
        -> 8
"""

 

 

## 의사코드 ##

# 애너그램이 되도록 제거해야 하는 최소 개수
# -> 두 단어에 공통으로 존재하는 알파벳의 개수를 len(a)와 len(b)에서 각각 빼서 더한 값

# 두 단어에 모두 존재하는 알파벳의 개수
# common = 0
# for s in a:
#     if s in b:
#         common += 1

# 제거해야 하는 최소 문자의 수 = (len(a) - common) + (len(b) - common)

 

 

 

첫 번째 시도

 

a = input()
b = input()

common = 0 # 두 단어에 공통으로 존재하는 알파벳의 개수
for s in a:
    if s in b:
        common += 1

print((len(a) - common) + (len(b) - common))

 

-> 틀림

 

 

 

통과한 코드

 

from collections import Counter
a = Counter(input())
b = Counter(input())

print(sum((a-b).values()) + sum((b-a).values()))

 

-> Counter()로 두 단어의 알파벳 개수를 각각 카운트하고, 두 딕셔너리의 차집합을 더한 값이 정답

 

 

• 과정 확인

"""
a: Counter({'a': 2, 'b': 2, 'c': 2})
b: Counter({'x': 2, 'y': 2, 'b': 2}) 

a-b: dict_values([2, 2])
b-a: dict_values([2, 2]) 

8
"""

 

 

 

참고)

 

https://mylittletechdiary.tistory.com/entry/%EB%B0%B1%EC%A4%80Python-1919-%EC%95%A0%EB%84%88%EA%B7%B8%EB%9E%A8-%EB%A7%8C%EB%93%A4%EA%B8%B0

[백준/Python] 1919 : 애너그램 만들기