[2024] day 36. 387. First Unique Character in a String

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 2월 5일 (월)
Leetcode daily problem

387. First Unique Character in a String

https://leetcode.com/problems/first-unique-character-in-a-string/description/

Problem

문자열 s가 주어질 때, 문자열 s에서 중복되지 않는 첫 번째 문자열의 인덱스를 찾아 반환한다. 만약 중복되지 않은 문자열이 없으면 -1을 반환한다.

Solution

array

Collection의 Counter 함수를 사용해서 푸는 방법도 있지만, O(n)으로 풀기 위해서 먼저 문자열을 돌면서 문자열을 키, 빈도를 값으로 하는 해쉬 함수를 만들고(딕셔너리), 다시 문자열을 인덱스를 중심으로 돌면서 문자열을 키로하고 빈도를 값으로 하는 해쉬 함수에서 값이 1이 처음 나올 때의 인덱스를 반환한다.

Code

class Solution:
    def firstUniqChar(self, s: str) -> int:
        cnt = {}

        for c in s:
            cnt[c] = 1+cnt.get(c,0)

        for i in range(len(s)):
            if cnt[s[i]] == 1:
                return i

        return -1

Complexicity

시간 복잡도

문자열 만큼 탐색하기 때문에 시간 복잡도는 O(n)이다.

공간 복잡도

문자열 s의 길이에 비례하는 추가적인 공간을 사용하지만,
딕셔너리의 cnt를 사용하여 각 문자의 등장 횟수를 저장해서 O(1)만큼의 공간을 사용한다.

---