[Q1:Korean] Anagram, 철자 확인

👇🏻 문제

문자열 s1, s2가 주어졌을 때, 그들이 anagram인지 확인해라. 두 문자열이 같은 빈도의 같은 문자로 이루어졌다면 anagrams가 맞다.

예시 ) s1 = "danger" , s2 = "graden" 은 anagram이다.

---

 [ 방법 1 ]

 

기본 로직

freq1 = s1의 문자들의 빈도수

freq2 = s2의 문자들의 빈도수

freq1 == freq2 👉🏻 s1과 s2는 anagram

 

이 로직을 수행하기 위해서는 a~z까지의 알파벳 테이블에 문자가 얼마나 들어갔는지 cnt를 계산해서 비교할 수 있다.

하지만, Hash Table 을 쓰면 되는데 용량 낭비까지 할 필요는 전혀 없다.

 

s1 = "nameless" , s2 = "salesman"

해쉬테이블

 

freq1 == freq2  => s1과 s2는 anagrams

 

 

 

 

 

구현

로직대로 구현한 코드

 

위와 같이 구현해도 되지만, 파이썬에 있는 Counter을 사용하면 코드가 훨씬 간단해진다.

 

짠

 

 

 

 

공간복잡도 & 시간복잡도

공간복잡도 : O(n) [freq1, freq2 의 크기 O(n)+O(n)]

시간복잡도 : O(n) [반복문 O(n)+O(n)+O(n)]

 

 

 

 

 

 

 [ 방법 2 ] 

 

기본 로직

두 개의 문자열을 sorted해서 같은지 확인한다.

 

s1 = "nameless" , s2 = "salesman"

sorted(s1) = "aeelmnss"

sorted(s2) = "aeelmnss"

sorted(s1) == sorted(s2) 👉🏻 s1과 s2는 anagram

 

 

 

 구현

시간복잡도 : O(nlogn), 공간복잡도 : O(n)

 

 

 

 

공간복잡도 & 시간복잡도

공간복잡도 : O(n) [n+n]

시간복잡도 : O(nlogn) [정렬  O(nlogn)+O(nlogn)+n]