1-10 시간복잡도 질문입니다.

38군데 합격 비법, 2025 코딩테스트 필수 알고리즘

해결된 질문

작성

1. 현재 학습 진도

몇 챕터/몇 강을 수강 중이신가요? 1-10

2. 어려움을 겪는 부분

def find_not_repeating_first_character(string):
    alphabet_occurrence_array = [0] * 26

    for char in string:
        if not char.isalpha():
            continue
        arr_index = ord(char) - ord("a")
        alphabet_occurrence_array[arr_index] += 1

    not_repeating_character_array = []
    for index in range(len(alphabet_occurrence_array)):
        alphabet_occurrence = alphabet_occurrence_array[index]

        if alphabet_occurrence == 1:
            not_repeating_character_array.append(chr(index + ord("a")))

    for char in string:
        if char in not_repeating_character_array:
            return char

    return "_"

아래 부분에서 시간복잡도가 O(N²) 인 것 같은데 왜 O(N)인지 궁금합니다.

for 문은 O(N) 인 건 알겠습니다!
if문에서 char가 not_repeating_character_array 리스트에 포함되어있는지 최악의 경우에 리스트 크기 만큼 돌아야하니까 O(N)라고 생각해서 총 시간복잡도는 O(N) * O(N) = O(N²) 로 계산했습니다...

    for char in string:
        if char in not_repeating_character_array:
            return char

python 코딩-테스트 알고리즘 data-structure

답변 2

딩코딩코

지식공유자

안녕하세요 홍비님!! 좋은 질문 감사합니다!!

말씀해주신대로 일반적인 인풋이라면 O(N) * O(N) = O(N^2) 으로 판단될 수 있는 상황입니다.

그러나, 코드의 not_repeating_character_array 의 길이에 따라서 상수시간으로 판단될 수 있는 코드입니다. not_repeating_character_array에는 알파벳 소문자만 들어갈 수 있습니다. 따라서 아무리 긴 문자열이 와도 not_repeating_character_array의 최대 크기는 26개를 넘을 수밖에 없습니다 따라서 if char in not_repeating_character_array: → O(26) = O(1) (상수시간) 으로 파악하게 되어 총 시간복잡도는 O(N) × O(1) = O(N)이 됩니다!

이 부분에 대해서 설명이 더 들어가면 좋았을 것 같습니다!!

좋은 질문 감사합니다 언제든 편하게 질문해주세요!!

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴입니다. 김홍비님.

질문하신 코드의 시간 복잡도에 대해 이해하는 것이 쉽지 않을 수 있습니다. 제공해주신 코드에서 의문점이 있는 부분에 대한 설명을 드리겠습니다.

코드 분석 및 시간 복잡도 설명

알파벳 빈도 계산:
- alphabet_occurrence_array를 생성하고 문자열을 순회하여 각 알파벳의 빈도를 기록합니다. 이는 O(N) 시간 복잡도를 가집니다.
중복되지 않는 문자 배열 구성:
- alphabet_occurrence_array를 순회하여 빈도가 1인 알파벳을 not_repeating_character_array에 추가합니다. 이 과정은 O(26), 즉 O(1)에 해당합니다. 알파벳의 개수는 상수이기 때문에 시간 복잡도는 O(1)로 간주합니다.
최종 문자 찾기:
- 최종적으로 문자열을 또 한 번 순회하며 not_repeating_character_array에 있는 첫 번째 문자를 찾습니다. not_repeating_character_array의 길이는 최악의 경우에도 알파벳 개수에 한정되므로, 최악의 경우 탐색은 알파벳 수에 비례하는 O(1)의 시간복잡도를 가집니다. 따라서 이 부분도 O(N)에 가깝게 수행됩니다.

종합적으로, 탐색 과정이 매우 빠른 이유는 not_repeating_character_array가 알파벳의 최대 크기에 불과하기 때문입니다. 일반적인 리스트 탐색이 O(k)의 시간 복잡도를 갖지만, 이 경우 k는 알파벳의 개수로 제한되어 있습니다.

따라서 전체 시간 복잡도는 O(N) + O(1) + O(N)에 해당하여, 결국 O(N)으로 해석됩니다.

추가 개선 사항

코드를 개선하여 더욱 효율적으로 변환할 수 있는 방법도 있습니다. 주의할 점은 대소문자를 처리하는 방식이나 추가적인 상황을 고려하여 개선해보는 것도 좋습니다.

관련된 기존 질문 및 답변을 참고하여 더 많은 Insight를 얻어보세요:

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

인프런 커뮤니티 질문&답변