9549 암호화된 비밀번호

9549 암호화된 비밀번호 - 백준

• 문제 한줄 정리
  알파벳 소문자로만 이루어져있는 비밀번호를
  1. 원래 비밀번호에서 서로 다른 두글자를 횟수에 상관없이 교환하고
  2. 문자열 앞뒤로 갯수에 상관없이 알파벳 소문자를 삽입하여
  암호화된 비밀번호로 만들었다. 이때 암호화된 비밀번호가 원래 비밀번호로 복호화될 수 있는지를 판별해라.
• Basic Idea
  - original password에 있는 알파벳이 아닌 알파벳이 포함된 subarray of encryption password가 원래의 비밀번호가 될 가능성은 없다.
  • 만약 original password와 original password와 동일한 길이의 subarray of encryption password같은 개수의 알파벳이 존재한다면, 원래의 비밀번호로 복호화될 수 있음을 의미한다.
• What To Do?
  1. original password에 속한 알파벳의 A~Z 빈도수를 담는 array를 생성한다.
  2. original password와 길이가 같은 subarray of encryption password에 속한 알파벳의 A~Z 빈도수를 담는 array를 생성한다.
  3. 만약, 두 array의 모든 빈도수가 일치한다면, YES. 그렇지 않다면, NO.
• Algorithm Analysis
  The Length Of Orinal Password : M
  The Length Of Encryption Password : N
  Time Complexity : T(N,M) = θ(N×M)
  Space Compelxity : θ(N+M)
• Full Code
  github.com/ssuda0/BaekJoon/문자열 암호화/9549.cpp