Remove Vowels

Q: 문자열에서 모음을 어떻게 제거하나요?

문자열을 한 번 훑으면서 대소문자와 관계없이 a , e , i , o , u 가 아닌 각 문자를 빌더나 리스트에 복사하세요. 마지막에 이를 문자열로 결합하세요. 남겨 둔 문자의 순서와 대소문자는 원래대로 유지됩니다.

Q: 모음을 제거하는 시간 복잡도는 무엇인가요?

한 번 순회하는 데 O(n) 시간이 걸립니다. 각 문자에 대해 상수 시간의 모음 검사를 한 번씩 하기 때문입니다. 최악의 경우, 즉 s 에 모음이 전혀 없을 때 출력에 O(n) 공간이 필요합니다. 모음마다 replace를 한 번씩 호출하는 방법도 O(n) 이지만, 문자열을 열 번 읽습니다.

Q: 정규 표현식으로 모음을 제거할 수 있나요?

네. 대부분의 언어에서 패턴 [aeiouAEIOU] 을 빈 문자열로 바꾸면 한 번의 호출로 처리할 수 있습니다. 시간 복잡도는 반복문과 동일한 O(n) 이지만, 면접관은 보통 모음 검사와 결과를 만드는 방법을 확인할 수 있도록 반복문을 작성하라고 합니다.

Q: 문자열에서 모음을 제자리에서 삭제하면 안 될까요?

중간에서 문자 하나를 삭제하면 그 뒤의 모든 문자가 왼쪽으로 이동하므로, 여러 번 삭제하면 O(n²) 의 비용이 들 수 있습니다. 인덱스 두 개를 사용하면 O(n) 에 제자리에서 처리할 수 있습니다. 하나는 모든 문자를 읽고, 다른 하나는 다음에 유지할 문자를 씁니다. 하지만 대부분의 언어에서 문자열은 변경할 수 없으므로 새 문자열을 만드는 것이 일반적인 방법입니다.

입문배열과 문자열

+10

영문자로 이루어진 문자열 s가 주어집니다. 모든 모음을 삭제한 문자열을 반환하세요. 모음은 대문자와 소문자 모두 포함하여 a, e, i, o, u입니다. 여기서 y는 모음이 아닙니다. 남은 문자는 순서와 대소문자를 유지합니다.

함수

removeVowels(s: string) → string

sstring: 정리할 영문자 문자열
반환값string: s에서 모든 모음을 제거하고 나머지 문자는 원래 순서대로 유지한 것

제약 조건

1 ≤ s.length ≤ 3 × 10⁴
s에는 영어 알파벳(a부터 z까지, A부터 Z까지)만 포함되어 있습니다.
s에는 모음이 아닌 글자가 하나 이상 포함되어 있으므로, 답이 비어 있는 경우는 없습니다.

예제

입력: s = "Interview"
출력: "ntrvw"
설명: Interview에서 I, e, i, e를 삭제하면 n, t, r, v, w가 그 순서대로 남습니다. 대문자 I도 모음이므로 삭제됩니다.

입력: s = "rhythm"
출력: "rhythm"
설명: rhythm에는 a, e, i, o 또는 u가 없으므로 아무것도 삭제되지 않습니다. y는 모음 목록에 없으므로 그대로 남습니다.

입력: s = "EuropeanUnion"
출력: "rpnnn"
설명: EuropeanUnion의 열세 글자 중 여덟 글자는 모음이며, 대문자 E와 U도 포함됩니다. 남은 다섯 자음 r, p, n, n, n은 순서를 유지하여 rpnnn으로 읽힙니다.

제출 시 숨은 테스트 +17개

후속 질문

텍스트에 É나 ö처럼 어떤 유니코드 문자든 포함될 수 있다면 어떨까요? 그중 어떤 문자가 모음이며, 테스트는 어떻게 달라질까요?

힌트

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

3개 중 0개 열림

풀이

문자열의 중간에서 문자를 한 번에 하나씩 삭제하면, 빈자리를 메우기 위해 그 뒤의 모든 문자가 이동하므로 비용이 많이 듭니다. 더 나은 방법은 결과를 직접 만드는 것입니다. 문자열을 한 번 훑으면서 모음이 아닌 문자를 모두 복사하세요. 대문자 모음을 처리하는 방법과 결과를 조합하는 방법에 유의해야 합니다.

각 모음은 별도의 단계에서 삭제하세요

핵심 아이디어

대부분의 언어에서는 문자열에서 특정 문자 하나의 모든 사본을 한 번의 호출로 삭제할 수 있습니다. 해당 문자를 아무것도 없는 것으로 바꾸면 됩니다. 이 작업을 a e i o u A E I O U의 각 문자에 대해 한 번씩, 총 열 번 수행하면 모음이 하나도 남지 않습니다. 자음은 전혀 건드리지 않으므로 순서와 대소문자가 그대로 유지됩니다.

Interview의 경우 e에 대한 작업을 수행하면 Intrviw가 되고, i에 대한 작업을 수행하면 Intrvw가 되며, I에 대한 작업을 수행하면 ntrvw가 됩니다. 나머지 일곱 번의 작업에서는 삭제할 문자가 없습니다.

각 작업은 현재 문자열 전체를 읽으므로, 작업량은 약 10n개의 문자 처리 단계입니다. 10은 상수이므로 여전히 O(n)이지만, 글자 수가 3 × 10^4개라면 3 × 10^5단계를 수행하게 됩니다. 한 번만 훑으면 3 × 10^4단계면 되는 것과 비교해 보세요.

알고리즘

열 개의 모음 글자 aeiouAEIOU를 한 번에 하나씩 처리합니다.
각 글자에 대해 s에 있는 해당 글자를 모두 아무것도 없는 것으로 바꿉니다.
열 번의 처리가 끝나면 s에 남은 것을 반환합니다.

def removeVowels(s):
    for vowel in "aeiouAEIOU":
        s = s.replace(vowel, "")  # one full pass for this letter
    return s

자음을 유지하는 한 번의 패스

핵심 아이디어

작업을 뒤집어 보세요. 모음을 삭제하는 대신 나머지를 모두 모읍니다. s를 한 번 순회하면서 각 문자가 모음 10개 중 하나인지 확인합니다. 모음이 아니면 결과에 추가합니다. 읽는 순서대로 추가하고 문자를 바꾸지 않으므로 자음의 순서와 대소문자는 입력된 그대로 유지됩니다.

EuropeanUnion의 경우 순회하면서 E, u, o, e, a, U, i, o를 건너뛰고 r, p, n, n, n을 추가합니다. 결과는 rpnnn입니다.

각 문자마다 상수 시간 테스트(집합 조회, switch 또는 10글자 문자열에서 검색)가 한 번씩 필요하므로 시간 복잡도는 O(n)입니다. 문자를 빌더나 리스트에 모은 뒤 마지막에 한 번만 문자열로 변환하세요. 변경 불가능한 문자열에 +=를 사용해 늘리면 매 단계마다 문자열이 복사됩니다. 출력 자체가 O(n) 공간을 차지합니다.

알고리즘

결과를 위한 빈 빌더를 시작합니다.
s를 한 번에 한 문자씩 순회합니다.
문자가 aeiouAEIOU 중 하나가 아니면 빌더에 추가합니다.
빌더를 문자열로 반환합니다.

def removeVowels(s):
    vowels = set("aeiouAEIOU")
    kept = []
    for ch in s:
        if ch not in vowels:
            kept.append(ch)
    # Joining a list once avoids rebuilding the string on every character.
    return "".join(kept)

함정과 경계 사례

오답의 대부분은 모음 검사나 결과 문자열이 늘어나는 방식에서 발생합니다.

대문자 모음을 빠뜨리는 경우. aeiou만 검사하면 Interview는 ntrvw가 아니라 Intrvw가 됩니다. 열 개의 문자를 모두 검사하거나, 검사하기 전에 문자를 소문자로 바꾸고 출력에는 원래 문자를 유지하세요.
남길 문자의 대소문자를 바꾸는 경우. 검사를 간단히 하려고 문자열 전체를 소문자로 바꾸면 QUEUEING은 QNG가 아니라 qng가 됩니다. 검사할 복사본만 소문자로 바꾸고, 원래 문자를 추가하세요.
인덱스로 앞에서부터 순회하며 삭제하는 경우. s[i]를 제거하면 다음 문자가 위치 i로 이동하고, 이어서 i++를 실행하면 그 문자를 건너뛰므로 aab는 ab가 됩니다. 새 문자열을 만들거나, 읽기 위치와 쓰기 위치를 따로 두고 순회하세요.
반복문에서 +=를 사용해 변경 불가능한 문자열을 늘리는 경우. Java나 C#에서는 매 단계마다 문자열 전체를 복사하므로, 문자 3 × 10^4개에 대해 약 4.5 × 10^8번의 문자 복사가 발생합니다. 빌더나 리스트를 사용하고 한 번만 결합하세요.

자주 묻는 질문4

문자열에서 모음을 어떻게 제거하나요?

문자열을 한 번 훑으면서 대소문자와 관계없이 a, e, i, o, u가 아닌 각 문자를 빌더나 리스트에 복사하세요. 마지막에 이를 문자열로 결합하세요. 남겨 둔 문자의 순서와 대소문자는 원래대로 유지됩니다.

모음을 제거하는 시간 복잡도는 무엇인가요?

한 번 순회하는 데 O(n) 시간이 걸립니다. 각 문자에 대해 상수 시간의 모음 검사를 한 번씩 하기 때문입니다. 최악의 경우, 즉 s에 모음이 전혀 없을 때 출력에 O(n) 공간이 필요합니다. 모음마다 replace를 한 번씩 호출하는 방법도 O(n)이지만, 문자열을 열 번 읽습니다.

정규 표현식으로 모음을 제거할 수 있나요?

네. 대부분의 언어에서 패턴 [aeiouAEIOU]을 빈 문자열로 바꾸면 한 번의 호출로 처리할 수 있습니다. 시간 복잡도는 반복문과 동일한 O(n)이지만, 면접관은 보통 모음 검사와 결과를 만드는 방법을 확인할 수 있도록 반복문을 작성하라고 합니다.

문자열에서 모음을 제자리에서 삭제하면 안 될까요?

중간에서 문자 하나를 삭제하면 그 뒤의 모든 문자가 왼쪽으로 이동하므로, 여러 번 삭제하면 O(n²)의 비용이 들 수 있습니다. 인덱스 두 개를 사용하면 O(n)에 제자리에서 처리할 수 있습니다. 하나는 모든 문자를 읽고, 다른 하나는 다음에 유지할 문자를 씁니다. 하지만 대부분의 언어에서 문자열은 변경할 수 없으므로 새 문자열을 만드는 것이 일반적인 방법입니다.

Python

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

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

s = "Interview"

기대값

"ntrvw"