자바 알고리즘 문제 풀이 입문. 섹션4. HashMap, TreeSet (해쉬, 정렬지원 Set) : 아나그램

 

https://hyejin.tistory.com/1227

자바 알고리즘 문제 풀이 입문. 섹션4. HashMap, TreeSet (해쉬, 정렬지원 Set) : 학급 회장

-> 이전 문제 풀이 

 

 

 

2. 아나그램 

설명

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

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

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

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

 

입력

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

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

 

출력

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

 

예시 입력 1 

AbaAeCe
baeeACA

 

예시 출력 1

YES

 

예시 입력 2 

abaCC
Caaab

 

예시 출력 2

NO

 

 

문제 풀이 1

public String solution(String a, String b) {
    String answer = "YES";
    Map<Character, Integer> mapA = new HashMap<>();
    Map<Character, Integer> mapB = new HashMap<>();
    for (char c : a.toCharArray()) {
        mapA.put(c, mapA.getOrDefault(c, 0) + 1);
    }

    for (char c : b.toCharArray()) {
        mapB.put(c, mapB.getOrDefault(c, 0) + 1);
    }

    for (Character x : mapA.keySet()) {
        if (mapA.get(x) != mapB.get(x)) {
            return "NO";
        }
    }

    return answer;
}

👩🏻‍💻  : 나는 그냥 간단하게 HashMap 2개를 만들고 문자열 a, b 를 각각 Character 를 Key 로 하고 그 개수를 구해줬다. 

다음 mapA의 key 값을 가지고 mapB에 key 값을 get 해서 다르면 NO 를 리턴하도록 했다. 

(사실 Key 값이 없을 경우를 고려하지 않았는데 정답 나와서 이게 되나..? 싶긴 했다.) 

 

 

문제 풀이 2

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

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


    return answer;
}

👾 : 강사님은 문제를 더 간단하게 풀었다. 우선 Map은 하나만 사용해서 s1 문자열에서 Character를 key로 잡고 그 개수를 각각 구하긴 했다. (여기까지는 동일), 그 다음엔 s2는 Character로 문자 배열로 만든다음, 반복문을 돌리는데 우선 map에 해당 문자가 있는지 즉, key 값이 존재하는지 containsKey 메서드로 확인해서 없거나 혹은 map.get(x) 했는데 이미 문자배열을 개수가 0 이라는 건 문자 개수가 맞지 않다는 의미이므로 return NO를 해줬다. 

만약 key 값이 존재한다면 map에서 put를 하는데 해당 key 값의 개수를 가져와서 -1 해준다. 

 

굳이 Map을 두개 안만들고 풀 수 있었는데..!! 나는 굳이 두개 만들어서 비교했던 것 같다..