Count Vowels

Q: 문자열에서 모음의 개수를 어떻게 세나요?

카운터를 사용해 문자열을 한 번 순회합니다. 각 문자를 소문자로 변환하고 a , e , i , o 또는 u 인지 확인합니다. 해당하면 1을 더합니다. 반복문이 끝나면 카운터에 정답이 들어 있습니다.

Q: 모음 개수를 세는 시간 복잡도는 얼마인가요?

문자열의 길이가 n 일 때 시간 복잡도는 O(n) 입니다. 각 문자를 한 번씩 확인하고, 각 확인에서는 최대 5개의 문자와 비교하기 때문입니다. 추가 공간 복잡도는 O(1) 입니다. 카운터 하나와 고정된 모음 집합만 사용합니다.

Q: 이 문제에서 y는 모음인가요?

아니요. 영어 철자에서 y 는 rhythm 처럼 때때로 모음 역할을 하지만, 프로그래밍 문제에서는 거의 항상 모음을 a , e , i , o , u 로 정의하며, 이 문제도 그렇습니다. 문제에 y 가 포함되어 있다면 검사할 문자에 추가하세요.

입문배열과 문자열

+10

영문자로 이루어진 문자열 s가 주어집니다. 그 문자열에서 모음의 개수를 세어 그 수를 반환하세요. 모음은 대소문자에 관계없이 a, e, i, o, u입니다. 문자 y는 모음으로 세지 않습니다.

함수

countVowels(s: string) → integer

sstring: 스캔할 영문자 문자열
반환값integer: s에서 대문자와 소문자를 모두 합한 모음의 개수

제약 조건

1 ≤ s.length ≤ 5 × 10⁴
s에는 영어 문자만 포함됩니다(a부터 z까지, A부터 Z까지).

예제

입력: s = "Interview"
출력: 4
설명: 모음은 I, e, i, e입니다. 대문자 I는 소문자와 동일하게 세므로 답은 4입니다.

입력: s = "rhythm"
출력: 0
설명: rhythm에는 a, e, i, o 또는 u가 없습니다. y는 모음처럼 들리지만 목록에 없으므로 답은 0입니다.

제출 시 숨은 테스트 +18개

후속 질문

문자열을 한 번만 읽으면서 다섯 개의 모음이 각각 몇 번 나타나는지 반환할 수 있나요?

힌트

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

3개 중 0개 열림

풀이

개수를 세려면 카운터를 사용해 문자열을 한 번 순회하면 됩니다. 결정할 사항은 문자가 모음인지 확인하는 방법과 대문자를 어떻게 처리할지뿐입니다. 각 문자를 소문자로 변환한 뒤 다섯 모음과 비교하면, 각 문자에 드는 작업량은 일정합니다.

각 모음을 별도의 패스로 세기

핵심 아이디어

질문을 열 개의 작은 질문으로 나누세요. a가 몇 개인지, e가 몇 개인지, 이런 식으로 U까지 세면 됩니다. 각 질문은 단순한 개수 세기입니다. 문자열을 순회하면서 문자가 찾으려는 글자와 같을 때마다 1을 더한 다음, 열 개의 개수를 모두 더하세요.

s의 모든 모음은 aeiouAEIOU의 열 글자 중 정확히 하나와 같으므로 정확히 한 번만 세어지고, 자음은 그 어느 글자와도 같지 않습니다. Interview의 경우 e를 확인할 때 2개, i를 확인할 때 1개, I를 확인할 때 1개가 나오고, 나머지 일곱 번은 아무것도 찾지 못합니다. 합계는 4개입니다.

문자열을 열 번 읽으므로 비교 횟수는 약 10n회입니다. 10은 상수이므로 여전히 O(n)이지만, 문자 수가 5 × 10^4개라면 한 번만 순회해서 각 문자를 한 번씩 읽는 경우와 달리 비교가 5 × 10^5회 발생합니다.

알고리즘

total = 0으로 설정합니다.
10개의 문자 aeiouAEIOU를 한 번에 하나씩 확인합니다.
각 문자마다 전체 문자열을 살펴보고, 문자가 해당 문자와 같을 때마다 total에 1을 더합니다.
10번의 반복이 끝나면 total을 반환합니다.

def countVowels(s):
    total = 0
    for vowel in "aeiouAEIOU":
        total += s.count(vowel)  # one pass over s for this letter
    return total

소문자 확인을 한 번 수행하기

핵심 아이디어

반복문의 순서를 바꾸세요. 문자열을 한 번 읽고, 각 문자에 대해 한 가지 질문을 하세요. 모음인가요? 한 번의 검사로 대문자와 소문자를 모두 처리하려면 먼저 문자를 소문자로 변환하세요. I는 i가 되고 E는 e가 되며, 자음은 그대로 자음이므로 a, e, i, o, u 다섯 글자만 비교하면 됩니다.

검사에는 상수 시간이 걸립니다. 다섯 글자에 대한 switch, 집합에서의 조회 또는 다섯 글자로 된 문자열 aeiou에서의 검색을 이용할 수 있습니다. Interview를 순회하면 I, e, i, e에서 카운터가 증가하고, 최종 값은 4입니다.

각 문자를 한 번씩만 읽으므로 시간 복잡도는 O(n)입니다. 메모리는 카운터와 다섯 개의 모음으로, 공간 복잡도는 O(1)입니다.

알고리즘

count = 0으로 설정합니다.
문자열을 한 번에 한 문자씩 순회합니다.
문자를 소문자로 변환합니다.
문자가 a, e, i, o 또는 u이면 count에 1을 더합니다.
count를 반환합니다.

def countVowels(s):
    vowels = set("aeiou")
    count = 0
    for ch in s:
        if ch.lower() in vowels:
            count += 1
    return count

함정과 경계 사례

이 작업은 몇 줄이면 충분하며, 오류는 첫 번째 검사에서 놓친 경우들 때문에 발생합니다.

소문자만 확인하는 경우. aeiou만 비교하면 Interview의 대문자 I를 놓쳐 3을 반환합니다. 문자를 소문자로 변환하거나 열 개의 문자를 모두 나열하세요.
y를 세는 경우. 이 문제에서 y는 모음이 아니므로 rhythm은 0을 반환합니다.
인덱스 0을 불일치로 처리하는 경우. "aeiou".indexOf('a')는 0이며, 이는 일치합니다. -1인지 검사하세요. 또는 PHP에서는 0 == false이므로 strpos를 false와 비교할 때 !==를 사용하세요.
C에서 루프 조건에 strlen(s)를 호출하는 경우. 매 반복마다 문자열 전체를 훑으므로 5 × 10^4개의 문자를 처리하는 데 약 2.5 × 10^9단계가 듭니다. '\0' 종결 문자에서 멈추거나 루프 전에 길이를 한 번 계산하세요.

자주 묻는 질문4

문자열에서 모음의 개수를 어떻게 세나요?

카운터를 사용해 문자열을 한 번 순회합니다. 각 문자를 소문자로 변환하고 a, e, i, o 또는 u인지 확인합니다. 해당하면 1을 더합니다. 반복문이 끝나면 카운터에 정답이 들어 있습니다.

모음 개수를 세는 시간 복잡도는 얼마인가요?

문자열의 길이가 n일 때 시간 복잡도는 O(n)입니다. 각 문자를 한 번씩 확인하고, 각 확인에서는 최대 5개의 문자와 비교하기 때문입니다. 추가 공간 복잡도는 O(1)입니다. 카운터 하나와 고정된 모음 집합만 사용합니다.

이 문제에서 y는 모음인가요?

아니요. 영어 철자에서 y는 rhythm처럼 때때로 모음 역할을 하지만, 프로그래밍 문제에서는 거의 항상 모음을 a, e, i, o, u로 정의하며, 이 문제도 그렇습니다. 문제에 y가 포함되어 있다면 검사할 문자에 추가하세요.

모음 확인에는 집합, switch 또는 문자열 검색을 사용해야 할까요?

다섯 글자이므로 세 방법 모두 문자당 일정한 시간이 걸리며, 속도 차이는 무시해도 될 만큼 작습니다. 사용하는 언어에서 가장 읽기 좋은 방법을 선택하세요. C, C++ 또는 Go에서는 switch를, Python, JavaScript 또는 Ruby에서는 집합이나 문자열 검색을 사용하면 됩니다.

Python

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

테스트 케이스

케이스 1

케이스 2

입력

s = "Interview"

기대값