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

Question

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

딩코딩코 · Answer

안녕하세요 홍비님!! 좋은 질문 감사합니다!!   말씀해주신대로 일반적인 인풋이라면 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 인턴 · Answer

안녕하세요, 인프런 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를 얻어보세요: 반복되지 않는 문자를 찾는 다른 방법 빈도 계산과 사용 예 저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.