JAVA 알고리즘 문제 - 아나그램(Anagram)

아나그램(Anagram)

 

설명

Anagram이란 두 문자열이 알파벳의 나열 순서를 다르지만 그 구성이 일치하면 두 단어는 아나그램이라고 합니다.

예를 들면 AbaAeCe 와 baeeACA 는 알파벳을 나열 순서는 다르지만 그 구성을 살펴보면 A(2), a(1), b(1), C(1), e(2)로

알파벳과 그 개수가 모두 일치합니다. 즉 어느 한 단어를 재 배열하면 상대편 단어가 될 수 있는 것을 아나그램이라 합니다.

길이가 같은 두 개의 단어가 주어지면 두 단어가 아나그램인지 판별하는 프로그램을 작성하세요. 아나그램 판별시 대소문자가 구분됩니다.

 

입력

첫 줄에 첫 번째 단어가 입력되고, 두 번째 줄에 두 번째 단어가 입력됩니다.

단어의 길이는 100을 넘지 않습니다.

 

출력

두 단어가 아나그램이면 “YES"를 출력하고, 아니면 ”NO"를 출력합니다.

 

입력 예시

AbaAeCe
baeeACA

 

출력 예시

YES

 

전체코드

import java.util.HashMap;
import java.util.Scanner;

public class Main {
	
	public String test(String A, String B) {
		String answer ="YES";
		HashMap<Character, Integer> map = new HashMap();
		
		for(char x : A.toCharArray()) {
			map.put(x, map.getOrDefault(x, 0)+1);
		}

		for(char x : B.toCharArray()) {
			if(!map.containsKey(x) || map.get(x) ==0) {
				answer = "NO";
			}else {
				map.put(x, map.get(x)-1);
			}
		}
		return answer;
	}
	
	public static void main(String[] args){
		Main t = new Main();
		Scanner kb = new Scanner(System.in);
		
		String strA = kb.next();
		String strB = kb.next();
		
		System.out.println(t.test(strA, strB));
    }
}

---

기본 설정으로 answer = "YES" 값을 설정해두고 입력받은 문자열 A를 map에 한글자씩 집어 넣는다.

	public String test(String A, String B) {
		String answer ="YES";
		HashMap<Character, Integer> map = new HashMap();
		
		for(char x : A.toCharArray()) {
			map.put(x, map.getOrDefault(x, 0)+1);
		}

		for(char x : B.toCharArray()) {
			if(!map.containsKey(x) || map.get(x) ==0) {
				answer = "NO";
			}else {
				map.put(x, map.get(x)-1);
			}
		}
		return answer;
	}

 

입력 받은 문자열  A -  AbaAeCe

		for(char x : A.toCharArray()) {
			map.put(x, map.getOrDefault(x, 0)+1);
		}

Key	Value
A	2
b	1
a	1
e	2
C	1

이와같은 형태의 map이 완성된다.

 

 

입력 받은 문자열 B - baeeACA

		for(char x : B.toCharArray()) {
			if(!map.containsKey(x) || map.get(x) ==0) {
				answer = "NO";
			}else {
				map.put(x, map.get(x)-1);
			}
		}
		return answer;

map에서 해당 문자열을 Key값으로 가지고 있지 않거나 해당 Key의 Value가 0이라면 결과값을 "NO"로 설정해준다.

 

Key의 존재 유무를 확인하는 경우 containsKey를 사용한다. 

여기서 map.get(x) ==0 이부분이 꼭 필요한가 처음에는 이해가 가지 않았는데 그림을 그려보니 명확하게 이해가 갔다.

결과값이 NO로 반환되는 경우도한번 살펴보겠다.

 

입력받은 첫번재 문자열 - abaCC

Key	Value
a	2
b	1
C	2

이와같이 값이 세팅되어지고 아래의 코드를 거치는 과정을 살펴보자.

		for(char x : B.toCharArray()) {
			if(!map.containsKey(x) || map.get(x) ==0) {
				System.out.println("map.get(x)====> " + map.get(x) + "  | map.values()"+ map.values());
				answer = "NO";
			}else {
				map.put(x, map.get(x)-1);
			}
		}

 

두번째 입력받은 문자열 - Caaab

 

1. C를 탐색

C의 존재 유무를 탐색 , Key값이  C인 Value가 0이 아닌지 확인

조건이 만족함으로 Value -1 을 적용

Key	Value
a	2
b	1
C	1

 

2. a를 탐색

a의 존재 유무를 탐색 , Key값이  a인 Value가 0이 아닌지 확인

조건이 만족함으로 Value -1 을 적용

Key	Value
a	1
b	1
c	1

 

3. a를 탐색

a의 존재 유무를 탐색 , Key값이  a인 Value가 0이 아닌지 확인

조건이 만족함으로 Value -1 을 적용

Key	Value
a	0
b	1
c	1

 

4. a를 탐색

a의 존재 유무를 탐색 , Key값이  a인 Value가 0이 아닌지 확인

조건이 만족하지 않음으로 "NO"를 반환

여기서  map.get(x) ==0 해당 조건이 필요한 이유는 Value의 값이 0이라면 애초에 첫번째로 입력받은 문자열의 

x 값과 두번재 입력받은 x값의 갯수가 일치하지 않는다는 의미이다.

 

해당 조건이 없다면 Value는 -1... 가 되어 정확하게 카운팅이 되지 않기에 해당 조건이 필요하다.