Valid Anagram

/LeetCode

voldemort-anagram

볼드모트 중2병... 애너그램

문제 해석

요약

애너그램인지 판단하기.

전문

🇰🇷 번역

두 문자 s와 t가 주어지면, t가 s의 애너그램인지 결정하는 함수를 작성하시오.

Input Output
s = "anagram", t = "nagaram" true
s = "rat", t = "car" false

주의:
문자열은 모두 소문자라고 가정한다.

덧붙임:
input에 유니코드가 포함되어 있으면 어떻게 되는가?
그러한 경우, 해결책이 어떻게 되는가?

🇺🇸 원문

Given two strings s and t , write a function to determine if t is an anagram of s.

Input Output
s = "anagram", t = "nagaram" true
s = "rat", t = "car" false

Note:
You may assume the string contains only lowercase alphabets.

Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case? </detail

🤔 문제 해결 방법 구상

이 문제는 주어진 문자열들을 규칙에 따라 정렬(.sort())하고 문자열을 비교하면 된다. 유효한 애너그램이라면, 정렬해 놓은 문자열이 같기 때문이다. 그러나 앞서 말했듯이 정렬관련 메소드는 최대한 사용하지 않으려고 한다.

바코 Prep때 풀었던 문제이다. 그 당시엔 배열로 만들어서 이중으로 for문 돌리는 방법으로 풀었었다. Prep때다 보니, 시간복잡도보다 푸는 것 자체가 큰 의미였던 시기였기 때문에 그것만으로도 만족했었다ㅎㅎㅎ. 이젠 시간복잡도를 신경쓰면서 풀어봐야겠다.

  1. 일단 문자열의 길이가 다르면 false.
  2. 문자열 길이가 같다면, 기준 문자열인 s의 문자열 key, 개수를 값으로 저장한다.
  3. t를 순회하면서 개수를 파악하는데, value가 1 이상이면 감소시키고, key가 아예 없으면 false, value가 0이어도 false
  4. 모두 통과하면 true

코드 구현

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
const isAnagram = function(s, t) {
  if (s.length !== t.length) return false;

  let sMap = {};

  for (let i = 0; i < s.length; i++) {
    sMap[s[i]] ? sMap[s[i]]++ : (sMap[s[i]] = 1);
  }

  for (let i = 0; i < t.length; i++) {
    if (sMap[t[i]]) {
      sMap[t[i]]--;
    } else {
      return false;
    }
  }

  return true;
};

결과 분석

Runtime: 100 ms
Memory Usage: 38.3 MB

시간복잡도는 O(n), 공간복잡도는 O(n)이다. 기본적인 조건에는 얼추 맞춘 것 같다.
그렇다면 이제 덧붙임에 나온 유니코드가 주어졌을때 발생하는 문제를 해결해야한다.

🧐 개선

유니코드란 텍스트 인코딩의 표준으로, 문자가 각각 특정 코드와 매핑되어 있다. 전세계 웬만한 문자를 다 가지고 있어서 한글도 표현이 가능하다. 참고로, 영어 알파벳은 소문자와 대문자의 유니코드 값이 다르다. 만약 input으로 들어올 알파벳이 유니코드면 해결방법은 무엇인지가 덧붙임 문제이다.

string엔 문자를 유니코드로 변환시키는 charCodeAt()이라는 메소드가 있다. 이 메소드를 이용하여 문제를 해결해 봐야한다...

개선 코드

  1. 문자열의 길이가 다르면 false는 동일.
  2. 사용되는 알파벳은 총 26자이다. 그리고 각 알파벳마다 코드가 정해져있다는 것을 이용하자.
  3. 길이가 26인 배열을 하나 만들고, 인덱스가 각 코드의 자리가 된다. (a는 0번째, b는 1번째...)
  4. 배열이 모두 0이라면 true, 아니면 false.
const isAnagram = function(s, t) {
  if (s.length !== t.length) return false;

  let array = new Array(26).fill(0);
  let a = 'a'.charCodeAt(0);


  for (let i = 0; i < s.length; i++) {
    array[s.charCodeAt(i) - a]++;
    array[t.charCodeAt(i) - a]--;
  }

  for (const count of array) {
    if (count !== 0) return false;
  }

  return true;
};

개선 결과

Runtime: 68 ms
Memory Usage: 37.2 MB

유니코드를 고려한 코드이고, 시간복잡도는 O(n), 공간복잡도는 O(1)이다. s와 t의 길이에 상관없이, 항상 일정한(알파벳 개수인 26만큼의 Array) 공간복잡도를 가지기 때문이다.

마무리

첫 코드 통과는 비교적 생각하기 쉬웠는데, 유니코드를 생각해야하는 덧붙임에서 많은 시간을 소비했다. 많이 듣긴 했으나, 유니코드 자체가 익숙치 않아서 다룰때마다 초면같다...ㅋㅋㅋ 문자열에 관련된 문제는 유니코드를 이용하여 풀 수 있는지 한 번 더 생각해 봐야겠다.

Reference & Learn More

MDN charCodeAt()
MDN for...of

Tags
Comments