dared 에서 d 를 빼고, bread 에서 b 를 빼면 각각 ared, read로 애너그램을 만족한다고 한다.
여기서 핵심이 "단어의 순서를 바꿨을 때 같아진다" 라는 건 "서로 다른 각 단어의 갯수가 일치한다"와 같은 말이다. (즉, a는 1개, e는 1개, r는 1개...)
그럼 같은 알파벳의 갯수만 맞추면 애너그램이 된다.
다시말해, 애너그램이 되려면 같은 알파벳의 차이만큼이 필요하다.
(예를 들면, s = "aaaa" 고, b = "aa" 이면 s 에서 a 를 2개만 빼면 된다.)
각 알파벳의 빈도수(frequency)를 저장할 배열을 만든다. freS[26] 와 같이. (각 인덱스는 'a' 부터 대응)
그럼 'a'부터 'z' 까지 abs( freS[alpha] - freT[alpha] ); 를 누적시키면 된다.
댓글 없음:
댓글 쓰기