Strings: Making Anagrams

🔗 문제 링크

https://www.hackerrank.com/challenges/ctci-making-anagrams/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=strings

❔ 문제 설명

A student is taking a cryptography class and has found anagrams to be very useful. Two strings are anagrams of each other if the first string's letters can be rearranged to form the second string. In other words, both strings must contain the same exact letters in the same exact frequency. For example, bacdc and dcbac are anagrams, but bacdc and dcbad are not.

The student decides on an encryption scheme that involves two large strings. The encryption is dependent on the minimum number of character deletions required to make the two strings anagrams. Determine this number.

Given two strings, a and b, that may or may not be of the same length, determine the minimum number of character deletions required to make a and b anagrams. Any characters can be deleted from either of the strings.

Example

a = 'cde'
b = 'dcf'

Delete e from a and f from b so that the remaining strings are cd and dc which are anagrams. This takes 2 character deletions.

Function Description

Complete the makeAnagram function in the editor below.

makeAnagram has the following parameter(s):

• string a: a string
• string b: another string

Returns

• int: the minimum total characters that must be deleted

Input Format

The first line contains a single string, a.
The second line contains a single string, b.

⚠️ 제한사항

• $1 ≤ |a|, |b| ≤ 10^4$

• The strings a and b consist of lowercase English alphabetic letters, ascii[a-z].

---

💡 풀이 (언어 : Java)

Anagram 문제는 접해본적 있지만, 둘을 만족시키기 위해 삭제하는 개수 문제를 본것은 처음이다. 어떻게할까 고민하다가 아름다운 방법은 안떠올라서, 그냥 정렬한 상태로 이중 for문으로 체킹해서 같은 글자를 찾으면 카운팅하고 다음 루프에서 다시 계산 안되도록 두 문자 모두 이상한 문자로 바꿔주는 알고리즘을 작성했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	private static int makeAnagram(String a, String b) {
		int count = 0;
		char[] arrA = a.toCharArray(), arrB = b.toCharArray();
		int lenA = arrA.length, lenB = arrB.length;
		Arrays.sort(arrA);
		Arrays.sort(arrB);
		
		for (int i = 0; i < lenA; i++) {
			for (int j = 0; j < lenB; j++) {
				if (arrA[i] == arrB[j]) {
					count++;
					// 원소들은 모두 영어 소문자이므로 이미 한번 카운팅한 같은 값들 중복계산 안되게 특수문자로 바꿔줌
					arrA[i] = '!';
					arrB[j] = '@';
					break;
				}
			}
		}
		return lenA + lenB - count * 2;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String a = br.readLine(), b = br.readLine();
		System.out.println(makeAnagram(a, b));
		br.close();
	}
}