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는 세 번 나타납니다. y(인덱스 4)와 e(인덱스 8)는 모두 한 번씩 나타나며, y가 먼저 나오므로 답은 4입니다.

입력: s = "swiss"
출력: 1
설명: 문자 s는 세 번 나타납니다. 인덱스 1의 w와 인덱스 2의 i는 모두 한 번씩 나타나며, w가 먼저 나옵니다.

입력: s = "aabbcc"
출력: -1
설명: aabbcc의 각 문자는 두 번씩 나타나므로 답은 -1입니다.

후속 질문

문자들이 스트림에서 한 번에 하나씩 들어옵니다. 각 문자가 들어온 후 지금까지의 첫 번째 고유 문자를 어떻게 보고할까요?

힌트

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

3개 중 0개 열림

풀이

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

각 문자의 두 번째 복사본을 찾아보세요

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

핵심 아이디어

왼쪽부터 각 위치에 대해 문자열 전체를 훑어 같은 문자가 있는 다른 위치를 찾습니다. 양쪽을 모두 살펴보세요. 앞에 있는 같은 문자도 뒤에 있는 같은 문자만큼 해당 문자를 제외할 이유가 됩니다. 같은 문자가 없는 첫 번째 위치가 답입니다. coddycode에서는 0부터 3까지의 위치마다 같은 문자를 찾지만, 인덱스 4의 y는 같은 문자를 찾지 못합니다.

각 문자가 하나의 긴 덩어리로 이어져 있는 경우, 예를 들어 a 2000개 다음에 b 2000개가 오는 식이라면 첫 번째 같은 문자를 찾았을 때 멈추는 방법도 도움이 되지 않습니다. 각 탐색이 앞선 덩어리 전체를 지나가기 때문입니다. 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개면 모든 개수를 저장할 수 있으며, 문자의 코드에서 a의 코드를 뺀 값을 인덱스로 사용합니다.

첫 번째 순회에서 카운터를 채웁니다. coddycode에서는 y와 e만 최종 개수가 1입니다. 두 번째 순회에서는 문자열을 왼쪽부터 훑으며 개수가 1인 첫 번째 문자에서 멈춥니다. 이는 인덱스 4의 y입니다. n단계를 두 번 거치므로 시간 복잡도는 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이다.
원시 문자 코드를 사용해 카운터에 접근하는 것. a는 97이므로 카운터 26개의 범위를 훨씬 벗어난다.
인덱스 대신 문자를 반환하거나, Lua 또는 R에서 1부터 시작하는 인덱스를 반환하는 것.

자주 묻는 질문3

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

문자를 세고 문자열을 스캔하는 것은 각각 n단계를 거치는 두 번의 패스이므로, 시간 복잡도는 O(n)입니다. 26개의 카운터는 길이에 관계없이 같은 공간을 차지하므로, 추가 공간 복잡도는 O(1)입니다.

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

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

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

소문자만 사용하는 경우, 26개의 카운터로 이루어진 배열이 더 작고 빠릅니다. 문자열에 유니코드 텍스트처럼 어떤 문자든 들어갈 수 있다면 해시 맵이 적합합니다. 알고리즘은 동일합니다. 개수를 센 다음 문자열을 순회합니다.

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

테스트 #1

테스트 #2

테스트 #3

인자

s = "coddycode"

예상 출력