2. 아나그램(해쉬)

1. 문제

Anagram(아나그램) 나열 순서는 다르지만 그 구성이 일치하는 두 단어

아나그램이면 YES, 아니면 NO를 출력하시오.

대소문자는 구분한다.

 

2 - 1. 나의 풀이

아나그램인지 확인하기 위해 필요한 조건.

1. 순서는 상관없음

2. 문자와 해당 문자의 개수

 

문자를 key, 문자의 개수를 value로 하는 HashMap을 사용한다.

한 단어가 다른 단어를 포함하는 관계 ex(abc, abcd)일 경우를 생각해야한다.

 

map1의 key를 기준으로 두 단어의 value 비교하고

map2의 key를 기준으로 두 단어의 value를 비교했다.

근데 그냥 한 번만 비교해도 정답처리긴 하더라.... 머지 -> 문자열의길이도 같아야하므로 한번만 비교해도 된다!

 

근데 HashMap에 저장하기 위해 for문 두 번

두 HashMap을 비교하기 위해 for문 두 번

도합 네 번의 for문을 사용해서 먼가 줄일 수 있을거같은데 방법을 모르겠다... 흠...

 

2 - 2. 나의 코드

package HashMap_TreeSet;

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

public class HashMap_02 {
    public static String solution(String s1, String s2) {
        String answer = "YES";
        HashMap<Character, Integer> map1 = new HashMap<>();
        HashMap<Character, Integer> map2 = new HashMap<>();

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

        for (char key : map1.keySet()) {
            if(map1.get(key) != map2.get(key)) answer = "NO";
        }
        for (char key : map2.keySet()) {
            if(map1.get(key) != map2.get(key)) answer = "NO";
        }

        return answer;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s1 = sc.nextLine();
        String s2 = sc.nextLine();

        System.out.println(solution(s1, s2));
    }
}

 

3 - 1. 강의 풀이

나처럼 노가다식 비교를 하지 않고 논리적으로 접근함.

 

일단 Map1에 s1 한 문자씩 저장한다. (아래 표는 Map1)

key	A	B	C
value	2	2	1

위 상황에서 s2의 한 문자씩 map1의 해당 key값  value에서 -1을 한다.

1. 만약 s2의 문자가 map1에 없을 경우

2. map1의 value가 이미 0일 경우 ㅡ> s2가 해당 문자(key)를 더 많이 가지고있음

위 두 상황은 두 단어가 아나그램이 아닌 경우이므로 "NO"를 return 한다.

 

3 - 2. 강의 코드

package HashMap_TreeSet;

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

public class HashMap_02_solution {
    public static String solution(String s1, String s2) {
        String answer = "YES";
        HashMap<Character, Integer> map1 = new HashMap<>();

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

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

        return answer;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s1 = sc.next();
        String s2 = sc.next();

        /*System.out.println(s1);
        System.out.println(s2);*/

        System.out.println(solution(s1, s2));

    }

}

 

4. 얻어갈 점

솔직히 전으로 돌아가도 강의 풀이같은 방법은 생각 못할거 같다.

익숙해지고 문제를 많이 풀어보쟝!