---
# System prepended metadata

title: 애너그램 만들기
tags: [algo]

---

# [애너그램 만들기](https://www.acmicpc.net/problem/1919)
- input: 2개의 영어 단어
- output: 애너그램 관계를 만들기 위해 제거하는 최소 문자 수
- 문제 요약
    - 애너그램 관계는 순서를 바꿔서 같아질 수 있을 때(즉 구성요소의 수가 같을 때)
    - 애너그램 관계를 만들기 위해 제거한 문자 수를 구해야한다

## 일반화 원리
> 간단한 예시 만들기, 내가 푼 과정을 보고 일반화 원리 떠올리기, 그 일반화 원리를 다른 예시에 적용 
```
- dared / bread
- adder / abder
- aabbcc
- bbxxyy
```
- 두 문자열 각각 a~z의 수를 더하기 위해 0으로 초기화된 26개의 배열을 2개 만든다
- 26번 반복하는 반복문을 통해 두 개의 배열 값을 비교하는데 값이 다르면 차이의 절대값을 0으로 초기화된 count 변수에 누적해서 더한다. 
- count 변수를 출력한다. 

### 어떻게 일반화 원리를 떠올렸나
> 어떻게 문제 이해? 어떤 컴퓨터 개념을 이용?
- 두 개의 문자열에서 구성요소의 수가 다른 수를 누적해서 더한다.
- 소문자라면 `ord('a') - ord(c)` 값은 0부터 25가 되는데 이때 0은 a, 1은 b ... 25는 z라고 생각할 수 있다.

```python
first = input()
second = input()

f_arr = [0] * 26
s_arr = [0] * 26

for c in first:
    f_arr[ord('a') - ord(c)] += 1

for c in second:
    s_arr[ord('a') - ord(c)] += 1

count = 0

for i in range(26):
    if f_arr[i] != s_arr[i]:
        count += abs(f_arr[i] - s_arr[i])

print(count)

```
 

## 풀고나서
> 어떻게 풀었는지 되짚기, 가설/모듈을 잘 적용했는지, 더 나은 방법은 없는지, 유용했던 점 생각하고 일반화, 사용한 자료구조 및 알고리즘과 시간복잡도는?
- 며칠 전에 사용했던 ord 함수를 이용해 배열 인덱스에 활용하는 걸 다시 사용했다.
- 주어진 문자열에서 a~z까지의 수를 세는 문제가 떠올랐다. 
- 시간복잡도 O(N)