Valid Anagram

Q: Valid Anagram의 시간 복잡도는 얼마인가요?

문자를 세는 데는 O(n) 시간이 걸리고 O(1) 의 추가 공간이 필요합니다. 문자열의 길이와 관계없이 카운터 배열의 항목 수가 26개이기 때문입니다. 두 문자열을 정렬하는 데는 O(n log n) 시간이 걸리고, 정렬된 복사본을 만들기 위해 보통 O(n) 의 공간이 필요합니다.

Q: 애너그램을 확인할 때는 정렬하는 것이 나을까요, 아니면 세는 것이 나을까요?

이론상 세기는 O(n) 으로, O(n log n) 보다 빠르며, 한 글자가 초과 사용되는 즉시 멈출 수 있습니다. 정렬은 작성하기 더 간단하고 수정 없이 어떤 알파벳에도 사용할 수 있습니다. 면접에서는 먼저 정렬을 언급한 다음 세기 방식으로 개선하세요.

Q: 유니코드 문자가 포함된 애너그램은 어떻게 확인하나요?

26개의 카운터 배열을 문자에서 개수로 매핑하는 해시 맵으로 바꾸세요. s 의 각 문자마다 1을 더하고, t 의 각 문자마다 1을 빼고, 모든 개수가 0으로 끝나는지 확인하세요. 문자열은 바이트 단위가 아니라 문자 단위로 읽어야 합니다. 여러 바이트로 저장되는 문자도 한 번만 세어야 합니다.

쉬움해싱 정렬

+10

두 문자열은 서로의 문자를 재배열한 것으로, 같은 문자를 같은 횟수만큼 사용하면 애너그램입니다. 소문자 영어 문자로 이루어진 두 문자열 s와 t가 주어집니다. t가 s의 애너그램이면 true를 반환하고, 그렇지 않으면 false를 반환하세요.

함수

isAnagram(s: string, t: string) → boolean

sstring: 첫 번째 문자열, 소문자
tstring: s와 비교할 문자열
반환값boolean: s의 각 문자를 정확히 같은 횟수만큼 사용하면 true

제약 조건

1 ≤ s.length, t.length ≤ 2 × 10⁴
s와 t에는 소문자 영어 알파벳(a부터 z까지)만 포함되어 있습니다.
두 길이는 서로 다를 수 있습니다.

예제

입력: s = "listen"t = "silent"
출력: true
설명: 두 단어 모두 e, i, l, n, s, t를 하나씩 포함하므로, silent는 글자 순서를 바꾼 listen입니다.

입력: s = "aabb"t = "abbb"
출력: false
설명: 길이는 같고 둘 다 a와 b만 사용하지만, aabb에는 a가 두 개 있고 abbb에는 하나 있습니다. 글자뿐만 아니라 개수도 일치해야 합니다.

입력: s = "cat"t = "cast"
출력: false
설명: cast는 네 글자이고 cat은 세 글자이므로, cat의 글자 순서를 아무리 바꿔도 cast라고 쓸 수 없습니다.

제출 시 숨은 테스트 +19개

후속 질문

문자열에 a부터 z까지의 문자 대신 모든 유니코드 문자가 들어갈 수 있다면 어떨까요? 개수를 세는 방법을 어떻게 바꾸겠어요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

애너그램은 각 문자의 개수는 유지하고 순서는 버립니다. 따라서 문자가 어디에 있었는지는 잊고 각 문자가 몇 번 나오는지는 기억하는 각 문자열의 요약이 필요합니다. 정렬은 O(n log n)에 이 요약을 만들고, 26개의 카운터로 된 표는 한 번의 순회로 요약을 만듭니다.

두 문자열 모두 정렬하기

핵심 아이디어

정렬하면 문자열의 문자가 알파벳순으로 배열되고 각 문자가 원래 어디에 있었는지는 알 수 없게 됩니다. listen을 정렬하면 eilnst가 되고, silent도 마찬가지이므로 두 단어는 애너그램입니다. aabb는 aabb로, abbb는 abbb로 유지됩니다. 인덱스 1에서 다르므로 두 문자열은 애너그램이 아닙니다.

이 검사는 양방향으로 성립합니다. t가 s를 재배열한 것이라면 두 문자열은 각 문자를 같은 횟수만큼 포함하므로 정렬하면 같은 순서가 됩니다. 정렬된 순서가 같다면 t는 s의 문자들을 정확히 사용합니다.

먼저 길이를 비교하세요. 길이가 다른 문자열은 절대 애너그램이 아니므로 두 문자열을 정렬할 필요가 없습니다. 정렬에는 O(n log n) 시간이 들고, 대부분의 언어에서는 문자를 복사한 뒤 정렬하므로 추가 공간 O(n)이 필요합니다. n = 2 × 10^4일 때는 빠르지만, 빈도수를 세는 방법은 작업량이 더 적습니다.

알고리즘

s와 t의 길이가 다르면 false를 반환합니다.
각 문자열의 문자를 배열에 복사합니다.
두 배열을 정렬합니다.
정렬된 배열이 요소별로 같으면 true를 반환합니다.

def isAnagram(s, t):
    if len(s) != len(t):
        return False
    return sorted(s) == sorted(t)

각 글자 세기

핵심 아이디어

나타날 수 있는 문자는 26개뿐이므로, 26개의 원소로 이루어진 배열에 각 문자마다 카운터 하나씩 둡니다. 인덱스 0은 a, 인덱스 25는 z에 해당합니다. 문자의 인덱스는 해당 문자의 문자 코드에서 a의 코드를 뺀 값입니다. s를 순회하며 각 문자의 카운터를 1씩 증가시킨 다음, t를 순회하며 1씩 감소시킵니다.

일찍 멈출 수도 있습니다. 카운터가 0보다 작다는 것은 t에서 해당 문자가 s에서보다 더 많이 사용되었다는 뜻입니다. aabb와 abbb의 경우, s를 순회한 뒤 카운터는 a: 2, b: 2입니다. 그런 다음 t에서 b가 세 번 나오는데, 세 번째에 b가 -1이 되므로 그 자리에서 false를 반환합니다.

카운터가 음수가 되지 않았다는 것만으로 충분한 이유는 무엇일까요? 두 문자열의 길이가 같으므로, 두 번의 순회가 끝난 뒤 카운터의 합은 0입니다. 음수인 카운터가 하나도 없다면 양수인 카운터를 상쇄할 값이 없으므로 모든 카운터는 0이고, 각 문자의 개수가 일치합니다. 그래서 길이 검사는 단순한 지름길이 아니라 반드시 필요합니다.

각 문자열을 한 번씩 읽으므로 시간 복잡도는 O(n)입니다. 배열에는 길이에 관계없이 항상 숫자 26개가 들어 있으므로 추가 공간 복잡도는 O(1)입니다.

알고리즘

s와 t의 길이가 다르면 false를 반환합니다.
0이 26개인 배열을 만듭니다.
s의 각 문자에 대해 해당 카운터를 1 증가시킵니다.
t의 각 문자에 대해 해당 카운터를 1 감소시킵니다. 카운터가 0보다 작아지면 false를 반환합니다.
true를 반환합니다.

def isAnagram(s, t):
    if len(s) != len(t):
        return False
    counts = [0] * 26  # counts[0] is 'a', counts[25] is 'z'
    for ch in s:
        counts[ord(ch) - ord("a")] += 1
    for ch in t:
        index = ord(ch) - ord("a")
        counts[index] -= 1
        if counts[index] < 0:
            return False  # t uses this letter more often than s
    return True

함정과 경계 사례

대부분의 오답은 각 문자가 몇 번 나타나는지가 아니라 어떤 문자들이 나타나는지를 확인하거나, 길이 검사를 빠뜨려서 발생합니다.

문자 집합을 비교합니다. aabb와 abbb는 모두 정확히 a와 b를 사용하지만, 애너그램은 아닙니다.
t의 모든 문자가 s의 어딘가에 있는지 확인하면서 해당 문자를 지우지 않습니다. aab와 abb는 양방향으로 모두 이 검사를 통과합니다.
개수를 세는 방식에서 길이 검사를 건너뜁니다. s = ab이고 t = a일 때, 카운터가 0보다 작아지지 않으므로 코드가 잘못해서 true를 반환합니다.
문자 코드를 그대로 카운터 배열의 인덱스로 사용합니다. a는 97이므로 길이가 26인 배열의 범위를 훨씬 벗어납니다. 먼저 a의 코드를 빼세요. Lua와 R에서는 배열의 인덱스가 1부터 시작하므로 1을 더하세요.

자주 묻는 질문4

Valid Anagram의 시간 복잡도는 얼마인가요?

문자를 세는 데는 O(n) 시간이 걸리고 O(1)의 추가 공간이 필요합니다. 문자열의 길이와 관계없이 카운터 배열의 항목 수가 26개이기 때문입니다. 두 문자열을 정렬하는 데는 O(n log n) 시간이 걸리고, 정렬된 복사본을 만들기 위해 보통 O(n)의 공간이 필요합니다.

애너그램을 확인할 때는 정렬하는 것이 나을까요, 아니면 세는 것이 나을까요?

이론상 세기는 O(n)으로, O(n log n)보다 빠르며, 한 글자가 초과 사용되는 즉시 멈출 수 있습니다. 정렬은 작성하기 더 간단하고 수정 없이 어떤 알파벳에도 사용할 수 있습니다. 면접에서는 먼저 정렬을 언급한 다음 세기 방식으로 개선하세요.

유니코드 문자가 포함된 애너그램은 어떻게 확인하나요?

26개의 카운터 배열을 문자에서 개수로 매핑하는 해시 맵으로 바꾸세요. s의 각 문자마다 1을 더하고, t의 각 문자마다 1을 빼고, 모든 개수가 0으로 끝나는지 확인하세요. 문자열은 바이트 단위가 아니라 문자 단위로 읽어야 합니다. 여러 바이트로 저장되는 문자도 한 번만 세어야 합니다.

두 개의 카운터 배열 대신 하나의 카운터 배열을 사용하는 이유는 무엇인가요?

문자열마다 하나씩, 배열 두 개를 사용하는 방법도 있습니다. 각 문자열의 빈도를 센 다음 배열을 비교하면 됩니다. s에 대해서는 증가하고 t에 대해서는 감소하는 배열 하나를 사용하면 메모리를 절반만 사용하며, 카운터가 음수가 되는 순간 마지막 비교 루프 없이 false를 반환할 수 있습니다.

Python

def isAnagram(s, t):
    # 여기에 코드를 작성하세요

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

s = "listen"
t = "silent"

기대값

true