[1스4코2파] #144. Leetcode 242. Valid Anagram

gunny·2023년 5월 30일

242. Valid Anagram 242. Valid Anagram python Array & Hashing leetcode 242. Valid Anagram leetcode 242. Valid Anagram python

코딩테스트

목록 보기

145/530

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (144일차)
[4코1파] 2023.01.13~ (135일차)
[1스4코1파] 2023.04.12~ (46일차)
[1스4코2파] 2023.05.03 ~ (25일차)

Today :

2023.05.27 [144일차]

242. Valid Anagram

https://leetcode.com/problems/valid-anagram/description/

문제 설명

두 문자열 s, t가 주어졌을 때, t가 s의 anagram이면.true, 아니면 False를 반환한다.

Anagram은 원래 문자를 구성하고 있는 문자열을 정확히 한 번씩만 사용해 (재배열해서) 만들어지는 문자임

문제 풀이 방법

방법은 여러가지가 있는데, 먼저 두 문자를 정렬해서 같은지 다른지 확인하는 방법
그리고 Hash map을 사용해서, 각 문자를 구성하고 있는 문자열의 빈도를 hash map에 저장하고, 이를 탐색하면서 각 문자열 빈도가 다르면 False를 return 하도록 푼다.

두 방법은 각 다른 시간복잡도를 가지는데, hash map으로 구현하는 게 시간 복잡도 측면에서 효율적이다.

내 코드

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if sorted(s) != sorted(t):
            return False
        
        return True

두 문자열이 Anagram 이라면 같은 문자로 구성되어 있고 순서만 다를 것이기 때문에, 문자열을 따라서 정렬하면 둘 다 같은 결과가 나와야 하기 때문에 실용성은 좋은 코드이다.

하지만 이 알고리즘은 효율성 면에서는 최적은 아니기 때문에, 문자열에 포함된 문자의 출현 횟수가 같은지 검사하는 알고리즘으로 바꾸어 효율성 있는 코드로 바꾸면 더 좋을 것이다.
두 문자열이 동일한 문자 개수를 갖고 있다는 점을 이용해, 배열을 두개 사용해 각 문자열 내의 문자 출현 횟수를 기록하고 두 배열을 비교한다.

class Solution:
    def isAnagram(self, s:str, t:str)->bool:
        if len(s)!=len(t):
            return False
    
        cntS, cntT = {},{}
        for i in range(len(s)):
            cntS[s[i]] = 1+cntS.get(s[i],0)
            cntT[t[i]] = 1+cntT.get(t[i],0)
            
        for c in cntS:
            if cntS[c] != cntT.get(c,0):
                return False
            
        return True

증빙