[백준 1919, Java] 애너그램 만들기

문제

www.acmicpc.net/problem/1919

1919번: 애너그램 만들기

 

잘못한 생각

 

 애너그램의 정의는 "두 영어 단어가 철자의 순서를 뒤바꾸어 같아질 수 있을 때, 그러한 두 단어를 서로 애너그램 관계에 있다고 한다." 이다. 처음에 '순서를 뒤바꾸어'를  한 단어의 순서를 거꾸로 뒤집은 다음 다른 단어와 같아지는지를 확인하는 것으로 생각했다. 즉 asdf 와 fdsa가 있을 때 asdf 의 순서를 뒤집은 단어가 fdsa와 같으면 애너그램이라고 생각했다. 예시를 잘보자!

 

"예를 들면 occurs 라는 영어 단어와 succor 는 서로 애너그램 관계에 있는데, occurs의 각 문자들의 순서를 잘 바꾸면 succor이 되기 때문이다." 를 보면 한 단어의 순서를 아무렇게나 바꿀 수 있다는 걸 알 수 있다. 

 

풀이

예시에서 힌트를 얻었다.  occurs와 succor를 보면 구성하고 있는 알파벳과 그 수가 같다. 다시말해 occurs는 o가 1개, c가 2개, u가 1개, r이 1개, s가 1개 인데, 이는 succor도 마찬가지이다. 그래서 두 단어의 각 알파벳의 총갯수를 count하고 (o 2개, c 4개 ...) 거기에서 각 단어의 알파벳 갯수를 뺀다. 

 

 애너그램 관계에 있을 경우 최종 배열에 있는 count는 모두 0이 된다. 애너그램 관계이 있지 않은 경우 최종배열에는 count가 남아있게 되는데 해당 알파벳을 count만큼 제거하면 에너그램 관계가 된다. 

 

 

총 갯수 구하기

 

각 단어의 알파벳 갯수 빼기

 

 

 위의 풀이는 총 4번의 순회를 하게 되는데, 이를 줄일 수 있다. 처음에 occurs를 count한 배열에서 succor의 알파벳 카운트를 뺀다. 그렇게 되면 배열는 음수 or 0 or 양수가 남아있게 된다. 

 

 음수or양수의 의미는 그 수의 절댓값만큼 해당 알파벳이 더 있다는 의미이고, 0의 의미는 두 단어에서 해당 알파벳이 없거나, 그 수가 같다는 의미이다.

 

 애너그램 관계에 있으려면 각 알파벳의 갯수가 같아야하므로, 배열을 순회하며 각 수의 절댓값을 count한 뒤, 해당 count만큼의 알파벳을 제거하면 애너그램이 된다. 

 

 

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static int[] countAlphabet;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String word1 = br.readLine().trim();
        String word2 = br.readLine().trim();

        countAlphabet = new int[26];
        int result = getAnagramCount(word1, word2);

        bw.write(String.valueOf(result));
        bw.flush();
        br.close();
        bw.close();
    }
    public static int getAnagramCount(String word1, String word2){
        int toBeRemovedCount = 0;
        for(int index = 0; index<word1.length(); index++){
            ++countAlphabet[word1.charAt(index)-97];
        }

        for(int index =0; index<word2.length();index++){
            --countAlphabet[word2.charAt(index)-97];
        }

        for(int index = 0; index< countAlphabet.length; index++){
            int count = Math.abs(countAlphabet[index]);
            toBeRemovedCount += count;
        }

        return toBeRemovedCount;
    }
}