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

1. 현재 학습 진도

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

   

2. 어려움을 겪는 부분

재취준을 준비하면서 여러 기업의 코딩테스트를 봤었는데요.

항상 시간 예외성 검사에 걸려서 코딩테스트를 탈락합니다.

그래서 이 문제를 보면서도 시간을 최대한 줄이고자 노력했습니다. 

3. 시도해보신 내용

input = "abadabac"

def find_not_repeating_first_character(string):
    while True:
        found_flag = False

        if len(string) > 1:
            target_char = string[0]
            for compare_char_index in range(1,len(string)):
                if target_char == string[compare_char_index]:
                    found_flag = True
                    break

            if found_flag:
                string = string.replace(target_char, "")
            else:
                return target_char
        else:
            return "_"



result = find_not_repeating_first_character
print("정답 = d 현재 풀이 값 =", result("abadabac"))
print("정답 = c 현재 풀이 값 =", result("aabbcddd"))
print("정답 =_ 현재 풀이 값 =", result("aaaaaaaa"))

제가 봐도 가독성이 안좋긴한데.. 저는 이 문제를 풀면서 가장 먼저 생각한 것이 '이미 한번 훑은 알파벳에 대해서는 순회를 제외한다' 였거든요.

그런데 글을 쓰면서 다시 확인해보니 string을 replace할 때 오히려 더 시간이 늘어날 것 같기도 하구요.. ㅠㅠ

for문의 대상이 되는 객체를 for문 안에서 변경할 수 없기에 부득이하게 found_flag라는 변수를 선언해서 for문 밖에서 판단 후 replace 하는 식으로 코드를 작성했습니다.

궁금한 점이, 딩코딩코님은 이 접근법에 대해서 어떻게 생각하시나요? 저는 정말 간단할 수 있는 문제를 20분 정도의 시간을 고민하면서 풀었는데, 이런 부분 때문에 실제 코딩테스트를 응시할 때도 시간이 부족했습니다.. ㅠㅠ

코딩테스트를 보면 1 <= N <= 1,000,000,000

이런 식으로 제한을 두다 보니.. '길이 1억의 string이 주어졌을 때 전부 순회하면 시간이 너무 길어지지 않나..?' 하는 생각이 항상 발목을 잡는 것 같습니다..

이런 문제를 접근할 때 어떤 식으로 접근해야 할지 조언 부탁드립니다..

항상 좋은 강의 감사드립니다!! (_ _)