[HashMap] 2. 아나그램

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

 

 

<<풀이>>

 

-나의 풀이-

 

시간 복잡도 : O(N)

 

일단 ㅋㅋ 나의 풀이는 크게 이상이 없어보인다만,,  정답이 틀렸다!!

어디서 오류가 나는 것일까 ... 

import java.util.*;

class Main {
    public String solution(String a, String b) {
        HashMap<Character, Integer> map1 = new HashMap<>();
        HashMap<Character, Integer> map2 = new HashMap<>();
        String answer = "";

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

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

        for(char k : map1.keySet()) {
            if(!map2.containsKey(k)) answer = "NO";
            else {
                if(map1.get(k) != map2.get(k)) answer = "NO";
                else answer = "YES";
            }
        }

        return answer;
    }


    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        String a = in.next();
        String b = in.next();

        System.out.println(T.solution(a, b));
    }
}

 

이 풀이를 조금 수정해본 결과

 

import java.util.*;

class Main {
    public String solution(String a, String b) {
        HashMap<Character, Integer> map1 = new HashMap<>();
        HashMap<Character, Integer> map2 = new HashMap<>();
        String answer = "";
        if (a.length() != b.length()) {
            return "NO";
        }


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

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

        for(char k : map1.keySet()) {
            if(!map2.containsKey(k)) answer = "NO";
            else {
                if(map1.get(k) != map2.get(k)) {
                    answer = "NO";
                    break;
                }
                else answer = "YES";
            }
        }

        return answer;
    }


    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        String a = in.next();
        String b = in.next();

        System.out.println(T.solution(a, b));
    }
}

ㅋㅋㅋㅋ 바로 break를 추가하니 정답을 맞췄다 ㅋㅋㅋㅋㅋ

 

아아아 !!!!!!! 생각해보니 break를 안 하게 되면 NO가 되더라도 다시 돌아가서 비교하고 key 값의 value가 같아지면 YES로 바뀌기 때문에문제가 생기는 것이다 ㅋㅋ ㅠㅠㅠ

 

 

그리고 또 다른 풀이 

import java.util.*;

class Main {
    public String solution(String a, String b) {
        if (a.length() != b.length()) {
            return "NO"; // 길이가 다르면 아나그램이 아님
        }

        HashMap<Character, Integer> map1 = new HashMap<>();
        HashMap<Character, Integer> map2 = new HashMap<>();

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

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

        // map1과 map2가 동일한지 검사
        if (!map1.equals(map2)) {
            return "NO";
        }

        return "YES";
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        String a = in.next();
        String b = in.next();

        System.out.println(T.solution(a, b));
    }
}

 

두둥!!! ㅋㅋㅋㅋ 이게 뭐람 ... equals라는 메소드를 여기서 이용할 수 있다니 !!!

이렇게 되면 현재까지 equals 메서드를 재정의 해서 사용하고 있는 건 String과 HashMap이다 !!

 

아마 더 있을 거 같은데 한 번 찾아봐야겠다. 

 

 

-강사님 풀이-

 

강사님은 아나그램을 말하시는데 또 다른 방식으로 풀었다.

 

import java.util.*;

class Main {
    public String solution(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) return  "NO";
            map.put(x, map.get(x) - 1);
        }
        return answer;
    }
    
    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        String a = in.next();
        String b = in.next();

        System.out.println(T.solution(a, b));
    }
}

 

우선, HashMap을 통해 map에다가 키와 값을 넣은 뒤에, 비교 대상과 비교하면서 값에 -1을 한다.

만약 돌아가는 중에 키값이 없거나 이미 값이 0이라면 같은 상황이 아니기 때문에 return NO를 통해 빠져 나온다.

그냥 answer = "NO";를 하려면 거기서 끝이 나게끔 break를 걸어줘야 한다!!!

 

아니면 계속 돌아가고 다음 코드에서  map에 키 값이 null 상태에서 get을 하기 때문에 런타임 에러가 나게 된다.

 

return의 사용과 break의 사용에 대해 다시 한 번 생각해보는 좋은 문제였다 ㅎㅎ

 

<<추가 공부>>

 

return문 : 메서드 자체를 종료시킨다. 리턴 값이 void일 때 그냥 return; 을 해서 메서드를 종료할 수 있다. 

 

break문 : 반복문에서 탈출을 할 때 이용한다.

 

continue문 : break문 처럼 완전히 loop에서 빠져나가지 않고 loop 안에 있는 뒤의 코드를 생략하고 다시 반 복문을 돌린다.