다음 알고리즘의 경우 괜찮은 접근인지 궁금해요

Question

1. 현재 학습 진도

몇 챕터/몇 강을 수강 중이신가요? 1- 10
어떤 알고리즘을 학습하고 계신가요? 1 - 10

2. 궁금한 부분

def find_not_repeating_first_character(string):
    occurrence_array = find_alphabet_occurrence_array(string)

    for char in string:
        if occurrence_array[ord(char) - ord('a')] == 1:
            return char
    return "_"

def find_alphabet_occurrence_array(string):
    alphabet_occurrence_array = [0] * 26
    for char in string:
        index = ord(char) - ord('a')
        alphabet_occurrence_array[index] += 1
    return alphabet_occurrence_array

딩코딩코 선생님의 풀이와 다르게 반복된 값이 들어 있는 array에서 string의 element를 순회하면서 index의 빈도수를 조회하고 1이면 return 하도록 했는데 괜찮은 접근일까요?

딩코딩코 · Answer

안녕하세요 Tommy 님 좋은 질문해주셔서 감사합니다!!

두 코드를 비교해보면

원래 코드는
1. 알파벳 발생 빈도 계산
2. 한 번만 등장한 문자들의 배열 생성
3. 원래 문자열을 다시 순회하면서 처음 발견된 중복되지 않는 문자 반환
Tommy 님의 코드는
1. 알파벳 발생 빈도 계산(별도 함수로 분리)
2. 원래 문자열을 한 번만 순회하며 빈도가 1인 첫 문자 바로 반환

처럼 변경이 된 것 같습니다!

Tommy 님의 접근 방식이 실제로 더 효율적입니다!

함수를 분리하여 코드 가독성이 향상되었습니다.
중간 배열(not_repeating_character_array)을 만들지 않아 메모리 사용이 더 효율적입니다.
원래 코드는 문자열을 두 번 순회하지만, 질문자분의 코드는 한 번만 추가로 순회합니다.

또한 문제의 의도(첫 번째로 중복되지 않는 문자 찾기)를 정확히 구현했습니다. 아주 좋은 개선이라고 생각합니다!! 👍 👍

인프런 AI 인턴 · Answer

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

질문하신 코드에서는 문자열의 알파벳 빈도를 계산하여, 처음으로 중복되지 않은 문자를 찾는 방식을 사용하고 있습니다. 이 접근 방식은 효율적으로 문제를 해결할 수 있는 좋은 방법 중 하나입니다. 다음은 해당 코드에 대한 간단한 설명입니다:

코드 설명

find_alphabet_occurrence_array 함수는 문자열에서 각 알파벳의 빈도를 계산하여 이를 배열로 반환합니다. 이 배열의 각 인덱스는 알파벳 (‘a’부터 ‘z’)에 해당합니다.
find_not_repeating_first_character 함수는 주어진 문자열을 한 번 순회하며, 각 문자의 빈도가 1인 경우 해당 문자를 반환하는 방식입니다.

장점

시간 복잡도: 이 방식은 문자열을 한 번 순회하며 빈도를 계산하고, 다시 한 번 순회하여 처음으로 중복되지 않은 문자를 찾기 때문에 전체 시간 복잡도는 O(N)입니다. 이는 매우 효율적입니다.
가독성: 코드가 비교적 쉽게 이해할 수 있는 구조로 짜여져 있습니다.

개선점

대소문자 처리: 현재 코드에서는 소문자만 처리하고 있어, 대문자도 함께 처리하려면 추가적인 조치가 필요합니다. char.lower() 메서드를 사용하여 대소문자 구분 없이 처리할 수 있습니다.

아래는 개선된 예시 코드입니다:

def find_not_repeating_first_character(string):
    occurrence_array = find_alphabet_occurrence_array(string.lower())

    for char in string:
        if occurrence_array[ord(char.lower()) - ord('a')] == 1:
            return char
    return "_"

def find_alphabet_occurrence_array(string):
    alphabet_occurrence_array = [0] * 26
    for char in string:
        index = ord(char) - ord('a')
        alphabet_occurrence_array[index] += 1
    return alphabet_occurrence_array

코딩에 대한 질문 및 열정을 가지고 계신 부분이 인상적입니다.

관련된 기존 질문 및 답변을 통해 더 다양한 접근 방식을 참고해보세요:
- 반복되지 않는 문자를 찾는 다른 방법
- 빈도 계산과 사용 예

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

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