First Unique Character in a String

Q: 문자열에서 첫 번째 고유 문자의 시간 복잡도는 무엇인가요?

문자 수를 센 다음 문자열을 훑는 것은 각각 n 단계씩 두 번 순회하므로, 시간 복잡도는 O(n) 입니다. 26개의 카운터는 길이에 상관없이 같은 공간을 차지하므로, 추가 공간 복잡도는 O(1) 입니다.

쉬움해싱

+10

소문자 영어 문자로 이루어진 문자열 s가 주어집니다. 문자열 전체에서 정확히 한 번 나타나는 첫 번째 문자를 찾아 0부터 세는 해당 문자의 인덱스를 반환하세요. 모든 문자가 두 번 이상 나타나면 -1을 반환하세요.

함수

firstUniqChar(s: string) → integer

sstring: 검색할 문자열, 소문자만
반환값integer: 정확히 한 번 나타나는 첫 번째 문자의 인덱스이며, 그런 문자가 없으면 -1

제약 조건

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

예제

입력: s = "coddycode"
출력: 4
설명: coddycode에서 문자 c와 o는 두 번, d는 세 번, e는 한 번 인덱스 8에 나타납니다. 하지만 y도 인덱스 4에 한 번 나타나며, 이것이 먼저 나오므로 답은 4입니다.

입력: s = "swiss"
출력: 1
설명: swiss에서 문자 s는 세 번 나타납니다. 인덱스 1의 문자 w는 한 번 나타나고, 인덱스 2의 i도 마찬가지입니다. 이들 중 먼저 나오는 문자가 우선하므로 답은 1입니다.

입력: s = "aabbcc"
출력: -1
설명: aabbcc의 모든 문자가 두 번씩 나타나므로 고유한 문자가 없으며 정답은 -1입니다.

제출 시 숨은 테스트 +17개

후속 질문

문자가 스트림에서 한 번에 하나씩 도착하며, 각 문자가 도착한 후 지금까지 나온 문자 중 처음으로 한 번만 나타난 문자를 알려야 합니다. 답을 최신 상태로 유지하려면 어떻게 해야 할까요?

힌트

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

3개 중 0개 열림

풀이

처음 마주쳤을 때는 고유해 보이는 문자가 문자열의 맨 끝에서 반복될 수 있으므로, 왼쪽에서 오른쪽으로 한 번 훑어보는 것만으로는 충분하지 않습니다. 먼저 모든 문자의 개수를 센 다음, 두 번째 순회에서 각 위치의 문자가 고유한지 상수 시간에 확인할 수 있습니다.

각 문자의 두 번째 사본을 찾으세요

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

왼쪽부터 위치를 살펴보세요. 위치 i에서 같은 문자가 있는 다른 위치 j를 찾기 위해 문자열 전체를 검색하세요. 그런 위치가 없다면 s[i]는 고유하며, 왼쪽부터 살펴보고 있으므로 첫 번째 고유 문자입니다. i를 반환하세요. coddycode에서는 위치 0부터 3까지 각각 같은 문자가 있는 위치를 찾고, 위치 4의 y는 그런 위치를 찾지 못합니다.

검색 범위는 i의 앞과 뒤를 모두 포함해 문자열 전체여야 합니다. 문자열 앞쪽에 있는 같은 문자도 뒤쪽에 있는 문자만큼 해당 문자가 고유하지 않다는 뜻입니다.

대부분의 문자열에서는 같은 문자를 처음 찾았을 때 검색을 멈추면 도움이 되지만, 항상 그런 것은 아닙니다. 각 문자가 2000개의 a 다음에 2000개의 b가 이어지는 식으로 긴 구간 하나에 모여 있다면, 각 문자를 검색할 때마다 같은 문자를 찾기 전에 그보다 앞선 구간을 모두 지나가게 됩니다. n = 5 × 10^4일 때 비교 횟수가 10억 회를 넘어 가장 큰 테스트에서는 너무 느립니다.

알고리즘

왼쪽에서 오른쪽으로 각 인덱스 i에 대해:
i 이외의 모든 인덱스 j를 살펴보고, s[j]가 s[i]와 같은 첫 번째 인덱스에서 멈춥니다.
그러한 j가 없으면 i를 반환합니다.
모든 인덱스에서 같은 값이 있는 항목을 찾았다면 -1을 반환합니다.

def firstUniqChar(s):
    n = len(s)
    for i in range(n):
        repeated = False
        for j in range(n):  # look for another copy of s[i]
            if j != i and s[j] == s[i]:
                repeated = True
                break
        if not repeated:
            return i
    return -1

문자 수를 센 다음 스캔하기

핵심 아이디어

브루트 포스 방식은 모든 위치에서 다시 "이 문자가 다른 곳에도 나타나는가?"를 확인합니다. 대신 한 번만 세세요. 문자는 26개뿐이므로 26개의 카운터가 있는 배열이면 모든 개수를 저장할 수 있습니다. 인덱스 0은 a에, 인덱스 25는 z에 해당합니다. 문자의 인덱스는 해당 문자의 문자 코드에서 a의 코드를 뺀 값입니다.

첫 번째 순회에서 카운터를 채웁니다. coddycode의 경우 카운터에는 c: 2, o: 2, d: 3, y: 1, e: 1이 기록됩니다. 두 번째 순회에서는 문자열을 왼쪽부터 훑다가 문자의 개수가 1인 첫 번째 위치에서 멈춥니다. 그 위치는 인덱스 4의 y입니다. 질문은 알파벳에서 첫 번째 문자가 아니라 첫 번째 위치에 관한 것이므로, 두 번째 순회에서는 26개의 카운터가 아니라 문자열을 훑어야 합니다.

두 번의 순회에서 각각 문자열을 한 번씩 읽으므로 시간 복잡도는 O(n)입니다. 문자열이 얼마나 길든 카운터는 26개로 유지되므로 추가 공간 복잡도는 O(1)입니다.

알고리즘

0이 26개인 배열을 만드세요.
s의 각 문자에 대해 해당 카운터를 1 증가시키세요.
인덱스 0부터 s를 다시 순회하세요. 개수가 1인 문자의 첫 번째 인덱스를 반환하세요.
순회가 끝나면 -1을 반환하세요.

def firstUniqChar(s):
    counts = [0] * 26  # counts[0] is 'a', counts[25] is 'z'
    for ch in s:
        counts[ord(ch) - ord("a")] += 1
    for i, ch in enumerate(s):
        if counts[ord(ch) - ord("a")] == 1:
            return i
    return -1

함정과 경계 사례

대부분의 실수는 너무 일찍 결론을 내리거나 두 번째 순회에서 잘못된 대상을 순회해서 발생합니다.

위치 i 앞의 문자만 확인하는 경우입니다. abca에서 첫 번째 a 앞에는 같은 문자가 없지만, 그렇다고 해서 유일한 문자는 아닙니다.
두 번째 순회에서 문자열 대신 카운터 배열을 순회하는 경우입니다. ba에서는 1과 같은 첫 번째 카운터가 a에 해당하지만, 답은 인덱스 0에 있는 b입니다.
인덱스 대신 문자를 반환하거나 인덱스를 1부터 세어 반환하는 경우입니다. Lua와 R은 1부터 세므로, 반환하기 전에 1을 빼세요.
-1인 경우를 잊는 것입니다. aabbcc와 같은 문자열에는 유일한 문자가 없으며, 함수는 루프가 끝난 뒤에도 값을 반환해야 합니다.
문자 코드를 그대로 사용해 카운터를 인덱싱하는 경우입니다. a는 97이므로 길이가 26인 배열의 범위를 훨씬 벗어납니다. 먼저 a의 코드를 빼세요.

자주 묻는 질문4

문자열에서 첫 번째 고유 문자의 시간 복잡도는 무엇인가요?

문자 수를 센 다음 문자열을 훑는 것은 각각 n단계씩 두 번 순회하므로, 시간 복잡도는 O(n)입니다. 26개의 카운터는 길이에 상관없이 같은 공간을 차지하므로, 추가 공간 복잡도는 O(1)입니다.

문자열을 한 번만 순회해서 해결할 수 있나요?

네. 한 번 순회하면서 각 문자에 대해 처음 나타난 인덱스를 저장하거나, 다시 나타나면 중복된 것으로 표시하세요. 그런 다음 26개의 문자를 확인하고 한 번만 나타난 문자 중 가장 작은 인덱스를 선택하세요. 문자열은 한 번만 읽고, 마지막 확인에는 26단계가 걸립니다.

글자 수를 세려면 해시 맵을 사용해야 할까요, 배열을 사용해야 할까요?

소문자만 사용하는 경우, 26개의 카운터로 이루어진 배열이 해시 맵보다 더 작고 빠릅니다. 문자열에 유니코드 텍스트와 같이 어떤 문자든 들어갈 수 있다면 해시 맵이 적절한 선택입니다. 알고리즘은 동일합니다. 먼저 개수를 세고, 그런 다음 문자열을 훑습니다.

두 번째 패스는 왜 카운트가 아니라 문자열을 순회하나요?

개수는 어떤 글자가 고유한지만 알려 줄 뿐, 어디에 있는지는 알려 주지 않습니다. 답은 문자열에서 가장 먼저 나오는 고유한 글자이므로, 문자열을 순서대로 살펴보다가 개수가 1인 글자가 있는 첫 번째 위치에서 멈춰야 합니다.

Python

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

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

s = "coddycode"

기대값