인프런 커뮤니티 질문&답변
작성한 질문수
1-10강 문제풀이중...
해결된 질문
작성
·
159
·
수정됨
0
1. 현재 학습 진도
몇 챕터/몇 강을 수강 중이신가요?
섹션1에 10강을 수강하고있습니다
1-10. 알고리즘 더 풀어보기 (2)
2. 어려움을 겪는 부분
강사님께서 제공해주신 문제를 먼저 풀어보았는데
아래처럼 내장함수를 이용해서 풀어도 되나? 궁금합니다. 최대한 저런 함수 사용하지 않고 강사님께서 제공해주시는 풀이법으로 알고리즘을 공부하는게 맞는거같은데.. 저처럼 풀면 안되는건가 싶어서요...ㅠㅠ 알고리즘적인 생각이 아닌가도 싶고 ㅠㅠ 고민입니다!
일단 char로 순서대로 돌꺼고 어차피 갯수가 1이면 바로 char 을 return해 주면 되지 않을까? 해서 아래처럼 해보았습니다...
def find_not_repeating_first_character(string):
# 이 부분을 채워보세요!
for char in string:
if string.count(char) == 1:
return char
return "_"
이렇게 구체적으로 알려주시면, 더 정확하고 도움이 되는 답변을 드릴 수 있습니다! 😊
답변 1
1
안녕하세요 Hello World님! 좋은 질문 감사합니다.
내장함수를 이용해서 새로운 풀이방법을 고민해보시는 점 너무 좋습니다!!
충분히 알고리즘적인 생각이고, 좋은 접근법입니다!
다만, 시간 복잡도 적인 면에서 아쉬운 점이 있습니다.
string.count(char)를 사용하면, 사실상 문자열 전체를 매번 순회하게 됩니다. 따라서 각 문자마다 문자열을 전부 탐색하므로 시간 복잡도는 O(N) * N, 즉 O(N²)가 되어 매우 비효율적입니다.
for char in string 에서 O(N) 만큼, string.count(char) 에서 O(N) 만큼 소요하게 되어서 2중 반복문의 형태로 O(N²)의 시간이 소모되게 되는 것입니다.
반면, 아스키 코드를 활용하면 한 번의 순회로 빈도를 계산할 수 있어 O(1) * N, 즉 O(N)의 시간 복잡도로 훨씬 효율적입니다.
파이썬을 하다보면, 이처럼 내장함수라서 매우 간단해보이지만 생각보다 시간복잡도가 높은 함수들이 몇개 존재합니다. 따라서 이런 것들을 주의하면서 코드를 작성해야 할 것 같습니다
좋은 질문 감사합니다 새해 복 많이 받으세요!!