2 분 소요

Hash Table

문제

문제 링크

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: s = “anagram”, t = “nagaram” Output: true

Example 2:

Input: s = “rat”, t = “car” Output: false

Constraints:

  • 1 <= s.length, t.length <= 5 * 104
  • s and t consist of lowercase English letters.

Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?

스스로 고민

접근법

  • 오늘 풀었던 replace 함수를 활용해서 풀면 될거 같았다.
  • s 와 t 둘다 같은 문자가 존재하면 True 아니면 False를 반환하면된다.

의사코드

  • s 와 t 의 문자열 길이가 같은지 검사
  • 검사가 통과된다면 s 문자열을 반복문으로 쪼갬
  • 쪼개진 문자가 t 안에 있다면 t에서 지워줌 아닐 경우 문자가 다른거니 False 리턴

구현 코드

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) == len(t):
            for i in s:
                if i in t:
                    t = t.replace(i,"",1)
                else: return False
                
            return True
        else:
            return False

시간 복잡도와 공간 복잡도

시간 복잡도:

  • len(s)와 len(t)를 한 번씩 호출하여 길이를 비교하는 부분은 O(1) 다.
  • for 루프에서 s의 각 문자를 순회하며 t에서 해당 문자를 찾고 대체하는데, t의 길이에 비례하는 작업을 수행한다. 최악의 경우 각 문자마다 t에서 해당 문자를 찾고 대체하는데 O(n)의 시간이 소요된다. 여기서 n은 문자열의 길이다.
  • 따라서 전체적으로 isAnagram() 메서드의 시간 복잡도는 O(1 + n) = O(n) 다.

공간 복잡도:

  • 주어진 코드에서 추가적인 데이터 구조나 메모리를 사용하지 않고, 문자열의 대체와 비교만을 수행하므로 공간 복잡도는 상수다.
  • 따라서 공간 복잡도는 O(1) 다.

회고 과정

지금 코드에서 뭘 개선할 수 있지?

  • 반복문도 하나 밖에 없어서 결과가 좋을거라고 생각헀는데 결과가 좋지 않아서 어떻게 개선해야 좋을까 생각해봤는데 아무리 생각해도 떠오르는 방법이 없었다. 그래서 다른 사람이 어떻게 접근했는지를 봤다.

다른 사람 코드를 보고 그 기준으로 어떤 부분을 개선 할 수 있는지 최종 회고

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(t) != len(s):
            return False
        return Counter(s) == Counter(t)
  • collections 모듈의 Counter 클래스를 사용해서 문제를 해결한 케이스다.
  • 이 클래스는 컨테이너 내의 원소들의 개수를 셀 때 사용되는 클래스로 주로 문자열, 리스트, 튜플등의 컨테이너에 사용할 수 있다.
  • Counter 클래스를 사용하면 각 원소의 개수를 딕셔너리 형태로 표현해서 관리할 수 있다.

Counter

from collections import Counter

# 문자열의 각 문자 개수를 세기
s = "anagram"
counter_s = Counter(s)
print(counter_s)  # 출력: Counter({'a': 3, 'n': 1, 'g': 1, 'r': 1, 'm': 1})

# Counter 객체 활용하여 애너그램 여부 확인
t = "nagaram"
counter_t = Counter(t)
is_anagram = counter_s == counter_t
print(is_anagram)  # 출력: True

또 다른 코드

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        for i in 'qwertyuiopasdfghjklzxcvbnm':
            if s.count(i)!=t.count(i):
                return False
        return True
  • 애초에 라이브러리 없이 기본 내장함수만으로 문제를 해결한 케이스다.
  • 무지성이긴 하지만 내가 반복문을 사용했던 것과 비교하면 지금 방법이 훨씬 더 간결하고 가독성도 좋고 성능도 좋다.
  • 뭔가 무지성이라서 시간 낭비처럼 보이더라도 시도 해보는 습관을 가져야 겠다고 생각했다. 처음에 위와 비슷하게 생각했는데 뭔가 좀 아닌거 같아서 이전에 활용되었던 replace 함수를 사용했었다. 모든 부분에 정답은 없으니 너무 쉽게 판단 내리고 결론 짓지 않도록 노력해야겠다.

댓글남기기

참고