섹션 4. HashMap, TreeSet - 2. 아나그램(해쉬)

📌 문제 설명

Anagram(아나그램)이란 두 문자열이 알파벳의 나열 순서는 다르지만 각 문자의 구성과 개수가 동일한 경우를 말합니다.

예를 들어,

• AbaAeCe 와 baeeACA 는 대소문자를 구분해서 보면 각 알파벳의 개수가 동일하므로 아나그램입니다.
• 반면, abaCC 와 Caaab는 문자의 구성과 개수가 일치하지 않으므로 아나그램이 아닙니다.

문자열 두 개가 주어졌을 때, 이 두 문자열이 아나그램인지 판별하는 프로그램을 작성하세요.

---

📝 입력 & 출력

입력

• 첫 줄에 첫 번째 단어 (길이 ≤ 100)
• 두 번째 줄에 두 번째 단어 (길이 ≤ 100)
• 대소문자 구분 O

출력

• 두 단어가 아나그램이면 YES
• 아니면 NO

---

🔸 예제 입력 & 출력

예제 입력 1

AbaAeCe
baeeACA

 

예제 출력 1

YES

 

예제 입력 2

abaCC
Caaab

 

예제 출력 2

NO

---

💡 해결 방법

• 첫 번째 문자열을 순회하며 HashMap으로 각 문자의 개수를 저장합니다.
• 두 번째 문자열을 순회하면서
  • 해당 문자가 map에 존재하지 않거나,
  • 개수가 0이라면 → 아나그램이 아님 (NO 반환)
  • 아니라면 개수를 하나씩 감소
• 최종적으로 모든 조건을 만족하면 YES 반환

---

💻 코드 구현 (Java)

package partHashTree;

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

public class Problem2 {
	public String solution(String s1, String s2) {
		String result = "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 result;
	}

	public static void main(String[] args) {
		Problem2 T = new Problem2();
		Scanner kb = new Scanner(System.in);
		String s1 = kb.next();
		String s2 = kb.next();
		System.out.print(T.solution(s1, s2));
		kb.close();
	}
}

---

📖 코드 설명

• getOrDefault(x, 0)를 사용하여 존재하지 않는 key는 0으로 초기화
• 두 번째 문자열 검사 시,
  • 없거나 0개면 → 아나그램 조건 위반 → "NO" 반환
• 모든 문자 검사 후에도 문제가 없다면 → "YES"

---

⏳ 시간 복잡도 분석

• 문자열 길이 N에 대해 각각 한 번씩 순회 → O(N)
• HashMap의 삽입/조회 시간은 O(1)이므로
• 총 시간 복잡도: O(N)

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런