[Leetcode 아주 상세한 문제풀이] 242. Valid Anagram - 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 242번 문제 Valid Anagram 다.

우선 문제를 살펴보자.

 

리트코드 242번 문제 Valid Anagram 링크

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

Valid Anagram - LeetCode

 

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?

 

 

문제 설명

문제를 간략히 살펴보자. 인풋으로 문자열 s와 t가 주어진다. 있다 문자열 t가 문자열 s의 anagram인지 판별하는 문제다. 이 문제를 해결하기 위해 anagram이란 무엇인가 이해할 필요가 있다. 문제의 설명에 따르면 anagram이란 문자열 안의 문자를 재배열하여 다른 문자열을 만들 수 있는 문자열을 의미한다. 예를 들어 "eat"이란 문자열은 재배열을 통해 "tea"라는 문자열을 만들 수 있기 때문에 tea는 eat의 anagram이라고 할 수 있다 (그 반대의 경우도 마찬가지다). 여기서 재배열한 문자열의 특정 의미를 갖는지는 중요하지 않다.

이 문제에서 요구하는 것은 주어진 문자열 s와 t에 대하여 문자열 t가 문자열 s의 anagram인지 판별하는 것이다. 문제 예시 1번에서 보는 것처럼 anagram이란 문자를 재배열하여 또 다른 문자열 nagaram을 만들 수 있다. 따라서 nagaram은 anagram 문자열의 anagram이라고 할 수 있다. 문제 예시 2번의 경우 문자열 car를 어떻게 재배열 하더라도 rat를 만들 수 없으므로 이 경우 anagram이라고 할 수 없다. 이제 문제를 풀어보자.

 

 

문제 접근법

이 문제를 해결하기 위해서는 anagram의 특징에 대해 이해해야 한다.

Angram의 첫번째 특징은 문자열의 개수가 같다는 것이다.

정의에 따라 문자열을 재배열 할때 문자 개수 자체는 변하지 않으므로 anagram인 문자열 길이는 같아야 한다.

또 다른 특징은 문자열 내에 존재하는 특정 문자가 나타나는 빈도가 동일하다는 것이다.

문자를 어떤 식으로 재배열 하더라도 각 문자가 늘거나 줄어들지는 않으므로 각 문자의 빈도는 동일해야 한다.

따라서 우리는 우선 인풋으로 주어진 두 문자열의 길이를 서로 비교한다.

만약 두 문자열의 길이가 다르다면 절대로 anagram이 될 수 없다.

두 문자열의 길이가 같은 경우 그 다음으로 각 문자의 빈도를 확인한다.

Angram의 정의에 따라 재배열 하더라도 각 문자의 빈도는 달라지지 않는다.

마지막으로 각 문자 빈도가 인풋으로 주어진 두 문자열에서 같은 빈도로 나타나는지 확인한다.

만약 위 경우를 모두 만족한다면 인풋으로 주어진 두 문자열은 anagram이라고 할 수 있다.

이제 코드로 한 번 살펴보자.

 

 

문제 풀이

우선 두 문자열을 입력받을 함수를 정의해 준다. (line 1)

위에서 설명한 대로 첫 번째 과정은 두 문자열의 길이가 같은지 확인하는 것이다. (line 3)

만약 두 문자열의 길이가 같지 않다면 anagram이 아니므로 False를 리턴하고 종료한다. (line 4)

인풋으로 주어진 두 문자열의 길이가 같은 경우 다음 과정으로 각 문자 빈도를 확인한다.

문자 빈도를 확인하기 위해 dictionary를 만들어 준다. (line 7-8)

이제 우리는 문자열 s부터 문자들을 하나씩 탐색한다. (line 10)

이때 get 함수를 이용하여 count_s dictionary 안에 해당 문자가 있는지 확인한다.

만약 문자열이 이미 존재한다면 그 value 값을 가져오고 만약 없다면 0 (문자열 없음)를 입력한다.

그리고 해당 문자를 dictionary 안 해당 key에 해당하는 value에 +1 카운트 해준다. (line 11)

이 과정을 문자열 t에 대해서도 진행한다. (line 13-14)

이 과정을 마치고 나면 count_s와 count_t 두 dictionary에 두 문자열 s와 t의 문자 빈도에 대한 정보가 key-value값으로 업데이트 되어있는 상태다.

우리는 anagram을 판별하기 위하여 이 두 dictionary를 비교한다.

Anagram의 정의에 따라 두 문자열의 각 문자 빈도가 같아야 하므로 (dictionary가 동일해야 하므로) 만약 두 dictionary가 같을 경우 True를 리턴하고 종료한다. (line 17)

 

 

문제 풀이 코드

def is_anagram(s, t):
    # If the lengths of the strings are not the same, they cannot be anagrams
    if len(s) != len(t):
        return False
    
    # Count the occurrences of each character in both strings
    count_s = {}
    count_t = {}
    
    for char in s:
        count_s[char] = count_s.get(char, 0) + 1
    
    for char in t:
        count_t[char] = count_t.get(char, 0) + 1
    
    # Compare the counts for each character
    return count_s == count_t
 
# Example usage:
print(is_anagram("anagram", "nagaram"))  # Output: True
print(is_anagram("rat", "car"))          # Output: False