1919: 애너그램 만들기

• toc {:toc}

문제

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

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

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

입력

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

출력

첫째 줄에 답을 출력한다.

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

풀이

문자열의 문자를 배열에 옮기고 서로 개수를 비교하여 많은 것들은 제거한다.

(추가가 안되고 제거만 가능하기 때문)

// 애너그램 관계 만들기
// 애너그램 만들기 위해 몇 개의 문자를 제거해야 하는가?
#include <bits/stdc++.h>
 
using namespace std;
 
int first[30];
int second[30];
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    string a, b;
    int cnt = 0;
    cin >> a >> b;
    for(auto elem : a){
        first[(int)elem-97]++;
    }
    for(auto elem : b){
        second[(int)elem-97]++;
    }
 
    for(int i = 0; i<30; i++){
        if(first[i]!=0 || second[i]!=0){
            if(first[i]>second[i]){
                cnt += first[i] - second[i];
            }
            else if(first[i]<second[i]){
                cnt += second[i] - first[i];
            }
        }
    }
 
    cout << cnt << endl;
    return 0;
}

정답 풀이 (훨씬 간결하다)

1. 배열을 하나로 합침.
2. abs 함수로 불필요한 if문을 줄임. 절대값 알아두기.

// Authored by : twinkite
// Co-authored by : BaaaaaaaaaaarkingDog
// http://boj.kr/ae5d8d2f69f04530b4df0c591e9b07d5
#include <bits/stdc++.h>
using namespace std;
 
int arr[2][26], res;
string s1, s2;
 
int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
 
  cin>>s1>>s2;
  for(char c : s1)
    arr[0][c-'a']++;
  
  for(char c : s2)
    arr[1][c-'a']++;
  
  for(int i=0; i<26; i++)
    res += abs(arr[0][i]-arr[1][i]);
  
  cout << res;
}