2014년 7월 17일 목요일

1919 - 애너그램 만들기

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] ); 를 누적시키면 된다.

댓글 없음:

게시글 목록