Count a Character

Q: 면접에서 내장 count 함수를 사용해도 되나요?

일반적으로 그렇습니다. 비용이 얼마나 드는지 설명할 수 있다면요. Python의 str.count 와 비슷한 함수는 여전히 문자열 전체를 읽으므로 O(n) 입니다. 면접관이 요청하면 루프를 작성할 준비를 해 두세요.

입문배열과 문자열

+10

문자열 s와 단일 문자 c가 주어집니다. s에 c가 몇 번 나타나는지 반환하세요. 일치 여부는 대소문자를 구분합니다. B와 b는 서로 다른 문자입니다.

함수

countChar(s: string, c: string) → integer

sstring: 검색할 영문자 문자열
cstring: 계산할 한 글자
반환값integer: s의 문자 중 c와 같은 것은 몇 개인가요?

제약 조건

1 ≤ s.length ≤ 5 × 10⁴
s에는 영어 알파벳(a부터 z까지, A부터 Z까지)만 포함됩니다.
c는 정확히 하나의 영어 알파벳 글자입니다.

예제

입력: s = "Mississippi"c = "s"
출력: 4
설명: Mississippi에는 인덱스 2, 3, 5, 6에 s가 있으므로 답은 4입니다.

입력: s = "Banana"c = "b"
출력: 0
설명: Banana는 대문자 B로 시작하고, 여러분은 소문자 b를 찾고 있습니다. 일치하는 항목이 없으므로 답은 0입니다.

후속 질문

c가 ss처럼 여러 글자로 된 단어라면 어떨까요? 겹치는 일치 항목도 포함되나요? 그리고 루프는 어떻게 바뀌나요?

힌트

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

3개 중 0개 열림

풀이

s의 어떤 문자든 c일 수 있으므로, 각 문자를 한 번씩 살펴보고 일치하는 항목을 셉니다. 대소문자에 주의하세요. 대문자는 다른 문자입니다.

모든 c를 삭제하고 길이를 비교합니다

핵심 아이디어

모든 c를 제거한 s의 복사본을 만드세요. 제거할 때마다 복사본의 길이가 한 문자씩 짧아지므로, 길이의 차이가 개수입니다. Mississippi의 경우 복사본은 Miiippi입니다. 11에서 7을 빼면 4입니다.

시간 복잡도는 O(n)이지만, 복사본은 카운터에는 필요하지 않은 O(n)의 추가 메모리를 사용합니다.

알고리즘

c와 같은 모든 문자를 제외한 s의 복사본을 만듭니다.
s의 길이와 복사본의 길이를 측정합니다.
s의 길이에서 복사본의 길이를 뺀 값을 반환합니다.

def countChar(s, c):
    # Every c that disappears makes the string one character shorter.
    without = s.replace(c, "")
    return len(s) - len(without)

카운터를 사용한 한 번의 순회

핵심 아이디어

복사본을 만들지 말고 읽으면서 개수를 세세요. 카운터는 0에서 시작해 c와 같은 각 문자마다 1씩 증가합니다. 단순한 동등 비교를 사용하면 대문자가 소문자와 일치하지 않습니다.

각 문자는 한 번만 비교하고 카운터만 저장하므로 시간은 O(n), 공간은 O(1)입니다. 건너뛴 문자가 추가로 하나의 c일 수 있으므로 어떤 해법도 시간 복잡도 O(n)보다 나을 수 없습니다.

알고리즘

c에서 대상 문자를 읽고 count = 0으로 설정합니다.
s를 한 번에 한 문자씩 순회합니다.
문자가 대상 문자와 같으면 count에 1을 더합니다.
count를 반환합니다.

def countChar(s, c):
    count = 0
    for ch in s:
        if ch == c:
            count += 1
    return count

함정과 경계 사례

대소문자를 무시하는 경우. 양쪽 모두 소문자로 변환하면 Banana와 b를 비교할 때 1이 반환됩니다. 정답은 0입니다.
문자와 문자열을 비교하는 경우. Java, C, C++, C# 및 Go에서는 c가 문자열인 반면 s[i] 또는 s.charAt(i)는 문자 하나입니다. 루프 전에 한 번 c[0](또는 c.charAt(0))을 가져오세요.
Java에서 ==로 문자열을 비교하는 경우. String.valueOf(s.charAt(i)) == c는 객체의 동일성을 비교하므로 거의 항상 false입니다. char 값을 비교하세요.
C에서 루프 조건에 strlen(s)를 호출하는 경우. 매 단계마다 문자열을 다시 탐색하므로 5 × 10^4개의 문자에는 약 2.5 × 10^9 단계가 소요됩니다.

자주 묻는 질문3

문자열에서 특정 문자가 몇 번 나타나는지 어떻게 세나요?

0에서 시작하는 카운터로 문자열을 한 번 순회하면서 현재 문자가 원하는 문자와 같을 때마다 1을 더하세요. 이 방법은 O(n) 시간이 걸리고 추가 메모리는 O(1)이 필요합니다. 대소문자를 구분하지 않고 세려면 먼저 문자열과 문자를 모두 소문자로 바꾸세요.

면접에서 내장 count 함수를 사용해도 되나요?

일반적으로 그렇습니다. 비용이 얼마나 드는지 설명할 수 있다면요. Python의 str.count와 비슷한 함수는 여전히 문자열 전체를 읽으므로 O(n)입니다. 면접관이 요청하면 루프를 작성할 준비를 해 두세요.

모든 문자를 한 번에 어떻게 셀 수 있을까요?

한 번 순회하면서 해시 맵이나 영어 알파벳용 카운터 52개가 있는 배열에 문자별 개수를 기록하세요. 순회가 끝나면 어떤 문자의 개수든 한 번의 조회로 확인할 수 있습니다. 같은 문자열에서 여러 문자의 개수를 물어볼 때 이 방법을 사용하세요.

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

테스트 #1

테스트 #2

인자들

s = "Mississippi"
c = "s"

예상 출력