LeeCode[ 242 | Python ] Valid Anagram
업데이트:
문제
https://leetcode.com/problems/valid-anagram/?envType=study-plan-v2&envId=top-interview-150
s 와 t 두 문자열이 주어지면 t가 s에 대한 애너그램이 될 수 있는지 true, false를 반환해야하는 문제.
풀이
시도
실행 시간 : 27ms
메모리 : 13.7MB
- 두 문자열의 길이가 다르다면
False를 반환한다. - 주어진 문자열
t의 각 철자의 개수를 세어가며 1씩 더한다. s의 문자열의 철자 수를 세어가며 1씩 뺀다.- 이 때 0 미만으로 내려가는 수가 있다면
False를 반환한다.
- 이 때 0 미만으로 내려가는 수가 있다면
- 모든 코드가 성공적으로 수행됐다면
True를 반환한다.
이전 문제와 상당히 비슷한 문제이다.
다만 애너그램 관계인 문자열은 서로 길이가 같아야 한다는 특징이 있다.
이에 맞춰 이전 문제에 사용했던 코드를 사용해 빠르게 문제를 해결했다.
다만, ransomNote 문제와 로직이 같은 것도 찜찜하지만 그것 외로 길이가 같아야한다는 특징을 고려해 문제를 다른 측면으로 해결할 수 있을 것 같아 수정해보았다.
class Solution(object):
def isAnagram(self, s, t):
dic = {}
if len(s) != len(t):
return False
for i in t:
if not i in dic:
dic[i] = 1
else:
dic[i] += 1
for r in s:
if r in dic:
if dic[r] <= 0:
return False
else:
dic[r] -= 1
else:
return False
return True
번외 - 정렬
실행시간 : 43ms
메모리 : 14.9MB
두 문자열의 길이가 같음을 이용했다.
정렬하면 두 문자열이 일치해야함을 이용해 정렬하고 둘을 비교한 결과를 반환하게 했는데, 해시테이블을 이용한 솔루션보다 당연히 수행시간이 느리다.
class Solution(object):
def isAnagram(self, s, t):
return sorted(list(s)) == sorted(list(t))
번외 - 해시테이블
실행시간 : 26ms
메모리 : 15.3MB
길이가 같지 않으면 미리 종료시키고 같은 경우에는 주소 값을 공유하게 하였다.
하지만 순서가 뒤바뀌어 있는 애너그램의 경우 어떤 문자가 나타나지 않는다.
따라서 바로 값을 반환해서는 안되기 때문에 결국 문자열 순회를 마치고도 음수가 나타난 적이 있는지 딕셔너리의 값 리스트들을 다시 순회해야한다.
class Solution(object):
def isAnagram(self, s, t):
dic = {}
if len(s) != len(t):
return False
for i in range(len(s)):
if s[i] in dic:
dic[s[i]] += 1
else:
dic[s[i]] = 1
if t[i] in dic:
dic[t[i]] -= 1
else:
dic[t[i]] = -1
return len(list(filter(lambda x : x < 0, dic.values()))) < 1
생각 & 정리
조금이라도 성능이 좋은 코드가 무조건하고 좋은 코드일까 ?
이 문제를 풀면서 든 생각이다. 3개의 솔루션을 내며 나머지 2 개의 솔루션이 번외라는 이름을 달고 나온데는 악화면 악화였지, 특별한 개선점이나 성능 향상이 없었기 때문이다.
하지만 정렬을 이용한 간결한 것은 둘째 치고(너무 함축되어 있는 코드는 가독성을 해치니까 !) 의도가 명확히 드러난 코드라는 생각이 들었다.
첫번째 코드도 변수명을 제외하고는 나쁘지 않은 코드라는 생각이 들었지만, 한 눈에 의도를 파악하기는 힘들지도 모른다는 생각도 함께 떠올랐다.
다소 미묘한 성능의 차이나 크게 연연하지 않아도 되는 상황이라면 의도가 다분히 드러나는 코드도 좋은 코드가 아닐까 하고 생각해보았다.
댓글남기기