[자바 / Java] 백준 1919번 - 애너그램 만들기

[자바 / Java] 백준 1919번 - 애너그램 만들기

 

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

1919번: 애너그램 만들기

 

문제

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

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

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

입력

 

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

출력

첫째 줄에 답을 출력한다.

예제 입력 1 복사

aabbcc
xxyybb

예제 출력 1 복사

8

 

알고리즘 분류

• 구현
• 문자열

 

풀이로직

• 입력받은 str1, str2의 각 구성문자는 'a'~'z' 이내임
• str1, str2의 각 'a'~'z'의 갯수를 담는 int형 배열 countStr1, countStr2선언
• 삭제해야할 문자의 갯수를 담는 int형 cnt선언
• str1, str2의 길이만큼 for문을 각각 돌며 'a'~'z'의 갯수를 countStr1, countStr2에 대응되는 인덱스에 담기
  •  (예: countStr1[0], countStr[0]에는 각 문자열 중에서 'a'의 갯수를 담음)
  •   countStr1[str1.charAt(i)-'a']
• countStr의 길이만큼(26만큼) for문을 돌며 countStr1[i]- countStr2[i]를 비교,
•   ->countStr1[i]- countStr2[i] == 0이라면 str1, str2 내에 해당 문자의 값은 상쇄되므로 skip
•  -> countStr1[i]- countStr2[i] !=0 이라면, countStr1[i]- countStr2[i] 의 절댓값 만큼은 상쇄되지 않아 삭제해야 하므로, Math.abs()의 값을 cnt에 더한다
• for문을 다 돈 후, cnt 반환 

코드1

import java.util.*;
import java.io.*;

public class Main{
    public static void main(String[] agrs) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str1 = br.readLine();
        String str2 = br.readLine();
        int cnt = 0;
        int[] countStr1 = new int[26];
        int[] countStr2 = new int[26];
        
        for(int i=0; i<str1.length(); i++){
            countStr1[str1.charAt(i)-'a']++;
        }
       
        for(int i=0; i<str2.length(); i++){
            countStr2[str2.charAt(i)-'a']++;
        }
        
        for(int i=0; i<26 ; i++){
            int compare = countStr1[i] - countStr2[i]; 
            if(compare !=0) cnt += Math.abs(compare);
        }
        
        System.out.println(cnt);
    }    
}

코드2 : 중복된 부분 함수로 빼기

import java.util.*;
import java.io.*;

public class Main{

	public static int[] addAlphabetSum(String str){
    
    	int[] countStr = new int[26];    
    	for(int i=0; i<str.length(); i++){
            countStr[str.charAt(i)-'a']++;
        }
    	
        return countStr;
    }
    
    public static void main(String[] agrs) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str1 = br.readLine();
        String str2 = br.readLine();
        int cnt = 0;
        
        int[] countStr1 = addAlphabetSum(str1);
        int[] countStr2 = addAlphabetSum(str2);
        
        forn(int i=0; i<26 ; i++){
            int compare = countStr1[i] - countStr2[i]; 
            if(compare !=0) cnt += Math.abs(compare);
        }
        
        System.out.println(cnt);
    }    
}