16. Anagram(구글 인터뷰문제)

it 취업을 위한 알고리즘 문제풀이

문제

코드1

코드2

코드3

문제해결방법

• 코드2가 첫번째 풀이(퀵정렬로 둘다 정렬 시킨후 하나하나 비교하면서 체크)
  • 정렬도 하고 size도 구해야하는 코드 때문에 시간복잡도가 좋지 않음
  • 퀵정렬 연습으로 사용함
• 코드1
  • 첫 번째 문자를 기준으로 두 번째 문자와 비교한다.
  • 이때 체크 했던 문자가 다시 검사 되지 않도록 비교 기준이 되는 문자와 같은 문자가 두번째 문자열에 있다면 앞문자와 교환하면서 그렇다면 비교한 곳까지는 두번째 문자도 첫문자와 같은 문자가 된다. 여기까지는 다시 체크할 필요가 없어짐
  • 같은 문자가 없다면 교환하지 않도록 코드 작성했기 때문 이때 flag변수로 같은 문장 있었는지 체크하고 없다면 루프만 빠져나감
  • flag 문자는 기준문자가 바뀔 때마다 초기화해주어서 매번 교환을 했는지 점검이 필요함
  • flag문자로 YES, NO체크
• 코드3
  • 해싱법으로 풀이
  • 첫 번째 문자열과 두 번째 문자열에서 각 문자들의 개수를 카운팅
    • 대문자는 아스키 코드로 6590(26개)으로 126 인덱스에, 소문자는 97122(26개) 2752인덱스에 개수 카운팅
    • 전역 변수는 자동으로 0으로 초기화 됨
  • 카운팅된 수 비교하기
  • 다르면 루프문 종료