gkgk0231   3년 전

파이썬으로 운용하면서 각종 편리한 라이브러리나 함수들을 이용하는 경우가 많은데, 해당 라이브러리 들의 시간복잡도를 확인을 해야만 합니다.

개인적으로 이번 문제 풀면서 시간초과를 나오게 했던 파트는 바로 아래에요.

nl = list(map(int,input().split()))
chart = []

for ni in nl:
    if ni not in chart :
        chart.append(ni)


 nl는 number List 약자로 nl로 했으며 저기에 입력받은 숫자의 배열을 파이썬 리스트 타입으로 저장했어요.

밑에 chart도 리스트로 초기화 후 아래 for문에서 중복을 없앤 리스트 결과값을 받고자 했어요.

순수 로직과 구현 자체는 그다지 이상한 점은 없는데요.

하지만 간과한 부분은 바로 리스트는 in 키워드를 사용하면 o(N)라는거에요.

즉, chart는 리스트로 선언을 했으며 in 키워드를 통해 리스트 내 원소 유무 파악하는 건 시간복잡도가 O(N)라는 것입니다.

for문 자체에서 o(N), in 키워드에서 o(N) 겹쳐져서 o(N^2) 이 돼요. 그래서 해당 코드로 진행 시 저 부분만 수행하다가 시간초과가 났어요.


그래서 in 키워드 시간복잡도가  O(1)인 딕셔너리로 바꾸니 해당 파트에 막히는 게 없어졌네요.

다른 분들의 질문 글을 보니 파이썬이 아닌 다른 언어더라도 해당 언어에서 나름 편리하게 이용할 라이브러리를 활용해서 구현하는 사람도 보였어요.

예를 들어 C++의 STL인 vector가 자주 보이는데요. vector로 예를 들면 vector내 find 함수는 시간복잡도가 O(n)이에요.  따라서 for문 내 vector의 find이 계속 호출 되도록 구현을 했다면 이는 O(N^2)가 되니 거의 높은 확률로 시간초과가 날겁니다.

언어에서 지원해주는 sort함수는 대부분의 경우 O(nlogn) 이니 이걸 for문으로 돌리지 않는다면 이걸로 시간초과는 나지 않을 겉 같네요.

따라서 이번 문제에서 시간초과가 계속 난다면 어떻게 구현했는지 보고, 당연하게 사용했던 함수들의 시간복잡도를 구글에 찾아서 확인해보는 시간을 가지는 것도 좋아보여요.

sdpr   3년 전

글 잘 읽어보았습니다.

살짝 다른 이야기이긴 한데, 중복을 제거한 리스트를 얻는 방법에는 아래 방법도 있습니다.

시간복잡도는 말씀하신 것과 같은 O(N)입니다.

gkgk0231   3년 전

오오. 이런 방법도 있었군요. 감사합니다.

dhunter   2년 전

어설프게 직접 이진검색 구현한거보다 dict 이용하는게 훨씬 빠르군요... 고급 정보 감사합니다.

댓글을 작성하려면 로그인해야 합니다.