Count a Character

Q: 문자를 셀 때 대소문자를 구분하나요?

이 문제에서는 그렇습니다. B 와 b 는 서로 다른 문자이므로 Banana 에는 b 가 없습니다. 대소문자를 구분하지 않고 세려면 비교하기 전에 문자열과 문자를 모두 소문자로 변환하세요.

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

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

입문배열과 문자열

+10

문자열 s와 단일 문자 c가 주어집니다. s에 c가 몇 번 나타나는지 반환하세요. 대소문자를 구분합니다. B와 b는 서로 다른 문자이므로 c와 정확히 일치하는 경우만 셉니다.

함수

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에는 0부터 세었을 때 2, 3, 5, 6번 위치에 s가 있으므로 답은 4입니다.

입력: s = "Banana"c = "b"
출력: 0
설명: Banana는 대문자 B로 시작하지만, 검색 대상은 소문자 b입니다. 둘은 서로 다르므로 일치하는 항목이 없고 답은 0입니다.

제출 시 숨은 테스트 +18개

후속 질문

만약 c가 ss처럼 여러 글자로 된 단어라면 어떨까요? 겹치는 일치 항목도 세나요? 그렇다면 반복문은 어떻게 바뀌나요?

힌트

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

3개 중 0개 열림

풀이

s의 모든 문자를 한 번씩 살펴봐야 합니다. 어떤 문자든 c일 수 있기 때문입니다. 작업은 카운터를 사용해 한 번만 훑으면 됩니다. 사람들이 자주 헷갈리는 세부 사항은 대소문자(대문자는 다른 문자입니다)와, 일부 언어에서 문자를 한 글자짜리 문자열과 비교하는 것입니다.

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

핵심 아이디어

모든 c를 제거한 s의 복사본을 만드세요. 제거된 문자 하나마다 복사본의 길이가 1씩 줄어들므로, 두 문자열 길이의 차이는 c가 나타난 횟수와 정확히 같습니다. 대부분의 언어에는 제거를 대신 수행해 주는 replace 또는 delete 함수가 있습니다.

Mississippi와 s의 경우 복사본은 Miiippi입니다. 원래 문자열은 11자이고 복사본은 7자이므로 c는 4번 나타났습니다. Banana와 b의 경우 대문자 B는 일치하지 않으므로 아무것도 제거되지 않고, 차이는 0입니다.

작업은 s를 한 번 순회하므로 시간 복잡도는 O(n)입니다. 비용은 메모리입니다. 복사본은 s만큼 길어질 수 있어 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에서 시작하는 카운터를 사용해 s를 왼쪽에서 오른쪽으로 살펴보고, 현재 문자가 c와 같을 때마다 1을 더하세요. 일치 여부는 단순 동등 비교로 결정되므로 대문자는 소문자와 절대 일치하지 않습니다.

Mississippi에서는 인덱스 2, 3, 5, 6에서 카운터가 올라가고 최종 값은 4입니다. 각 문자는 한 번씩 비교되며, 그 밖에는 아무것도 저장되지 않습니다.

따라서 시간 복잡도는 O(n), 추가 공간 복잡도는 O(1)입니다. 카운터 하나와 대상 문자만 있으면 됩니다. 건너뛴 문자가 c일 수도 있으므로 시간 복잡도를 이보다 더 낮출 수는 없습니다.

알고리즘

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.charAt(i) 또는 s[i]는 단일 문자입니다. 반복문을 시작하기 전에 c[0] (또는 c.charAt(0))을 한 번 가져오세요.
Java에서 문자열을 ==로 비교하기. String.valueOf(s.charAt(i)) == c는 객체의 동일성을 비교하므로 거의 항상 거짓입니다. char 값을 비교하거나 equals를 사용하세요.
C에서 반복문의 조건식에 strlen(s)을 호출하기. 매 단계마다 문자열 전체를 훑으므로, 문자 5 × 10^4개를 처리하는 데 약 2.5 × 10^9번의 연산이 필요합니다. 대신 '\0' 종료 문자를 만날 때까지 반복하세요.

자주 묻는 질문4

문자열에서 특정 문자의 출현 횟수를 어떻게 세나요?

카운터를 0에서 시작하고 문자열을 한 번 순회하세요. 현재 문자가 찾고 있는 문자와 같을 때마다 1을 더하세요. 루프가 끝나면 카운터가 답이며, 실행 시간은 O(n)이고 추가 메모리는 O(1)입니다.

문자를 셀 때 대소문자를 구분하나요?

이 문제에서는 그렇습니다. B와 b는 서로 다른 문자이므로 Banana에는 b가 없습니다. 대소문자를 구분하지 않고 세려면 비교하기 전에 문자열과 문자를 모두 소문자로 변환하세요.

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

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

모든 문자를 한 번에 세려면 어떻게 해야 할까요?

한 번 순회하면서 해시 맵이나 영어 알파벳용 카운터 52개가 있는 배열에 각 문자의 개수를 기록하세요. 한 번 순회한 후에는 어떤 문자든 개수를 한 번의 조회로 확인할 수 있습니다. 같은 문자열에서 여러 문자의 개수를 묻는 경우에는 이 방법이 더 좋습니다.

Python

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

테스트 케이스

케이스 1

케이스 2

입력

s = "Mississippi"
c = "s"

기대값