[인프런] 아나그램램(해쉬)

난이도

• Easy

문제 설명

Anagram이란 두 문자열이 알파벳의 나열 순서를 다르지만 그 구성이 일치하면 두 단어는 아나그램이라고 합니다.
예를 들면 AbaAeCe 와 baeeACA 는 알파벳을 나열 순서는 다르지만 그 구성을 살펴보면 A(2), a(1), b(1), C(1), e(2)로 알파벳과 그 개수가 모두 일치합니다.
즉 어느 한 단어를 재 배열하면 상대편 단어가 될 수 있는 것을 아나그램이라 합니다.
길이가 같은 두 개의 단어가 주어지면 두 단어가 아나그램인지 판별하는 프로그램을 작성하세요. 아나그램 판별시 대소문자가 구분됩니다.

입력 형식

• String, String

출력 형식

• YES or NO

예제 입력 및 출력

**예제 1:**
입력 : AbaAeCe baeeACA
출력 : YES

**예제 2:**
입력 : abaCC Caaab
출력 : NO

접근 방법

• 해시맵 사용: 각 문자열을 key 로 하고, 문자열 수를 int로 하는 map 생성
• map 순환 : key가 존재하지 않거나, count 숫자가 다르면 NO

  시간 및 공간 복잡도

• 시간 복잡도: O(n) - 문자열을 한 번 순회 ( O(n))
• 공간 복잡도 : O(1) - 해시맵에 저장되는 요소는 최대 5개(A, B, C, D, E)로 고정되어 있으므로 입력 크기와 상관없이 상수 공간을 사용

코드 구현

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

        String answer = "YES";
        String firstText = sc.nextLine();
        String secondText = sc.nextLine();

        firstText = firstText.toLowerCase();
        secondText = secondText.toLowerCase();

        if(firstText.length() != secondText.length()){
            answer = "NO";
        }

        Map<Character, Integer> firstTextMap = new HashMap<>();
        Map<Character, Integer> secondTextMap = new HashMap<>();

        for(char c1 : firstText.toCharArray()){
            if(firstTextMap.get(c1) != null){
                firstTextMap.put(c1, firstTextMap.get(c1) + 1);
            }else{
                firstTextMap.put(c1, 1);
            }
        }

        for(char c2 : secondText.toCharArray()){
            if(secondTextMap.get(c2) != null){
                secondTextMap.put(c2, secondTextMap.get(c2) + 1);
            }else{
                secondTextMap.put(c2, 1);
            }
            
        }

        for(Character key : firstTextMap.keySet()){
            if(firstTextMap.get(key) == null ||
                secondTextMap.get(key) == null ||
                firstTextMap.get(key) != secondTextMap.get(key)
            ) {
                answer = "NO";
            }
        }
        System.out.println(answer);
    }

코드 개선

• 두 번째 문자열을 map으로 만드는 것이 아니라 직접 비교함

  public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
  
        String answer = "YES";
        String firstText = sc.nextLine();
        String secondText = sc.nextLine();
  
        firstText = firstText.toLowerCase();
        secondText = secondText.toLowerCase();
  
        if(firstText.length() != secondText.length()){
            answer = "NO";
        }
  
        Map<Character, Integer> firstTextMap = new HashMap<>();
  
        for(char c1 : firstText.toCharArray()){
            if(firstTextMap.get(c1) != null){
                firstTextMap.put(c1, firstTextMap.get(c1) + 1);
            }else{
                firstTextMap.put(c1, 1);
            }
        }
  
        for(char c2 : secondText.toCharArray()){
            if(!firstTextMap.containsKey(c2) || firstTextMap.get(c2) == 0){
                answer = "NO";
            } 
            firstTextMap.put(c, firstTextMap.get(c2) - 1);
        }
  
          
        System.out.println(answer);
    }