강의로 돌아가기
breadf1sh

효율성 문제 무엇일까요??

def solution(participant, completion):

participant.sort()
completion.sort()
for i in completion:

if i in participant:
participant.remove(i)

answer=participant[0]

return answer

처음에는 sort없이 했을땐 테스트케이스 4,5에서 시간이 4~5초로 나왔는데
sort쓰니까 1미만으로 나오더라구요.
효율성은 어느 부분을 고쳐야 할까요? for 안에 if in을 사용해서 시간복잡도가 늘어나서 그런가요?

작성중인 코드―solution.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def solution(participant, completion):

    participant.sort()
    completion.sort()
    for i in completion:


        if i in participant:
            participant.remove(i)



    answer=participant[0]


    return answer
1 개의 답변
Leni

제 경험아닌 경험상으로.. (추측) remove가 원인 인 것 같습니다.

def solution(participant, completion):

    participant.sort()
    completion.sort()

    # 수정할 부분 - - - - - 
    for i in completion:

        if i in participant:
            participant.remove(i)

    answer=participant[0]

    return answer
    # 수정할 부분 - - - - - 

해당부분을

for index in range(len(completion)):
            if completion[index] != participant[index]:
                # 동명이인 중에 완주 못한 사람 체크
                return participant[index]

        # 동명이인이고 완주를 하지 못했으나 이름 상 제일 뒤에 있는 사람인 경우 체크
        # 예시) 정렬된 후의 변수가 participant['a', 'b', 'b', 'z', 'z'] / completion['a', 'b', 'b', 'z'] 인 경우
        return participant[-1]

로 바꾸신다면 동명이인이 여려명 일 경우에도 잡아내실 수 있습니다 :)

  • 김인규
    궁금한 점이 있습니다. index로 접근하는 건 participant와 completion이 sort되었을 경우에만 적용 할 수 있는 거죠? 김인규 2019.03.01 17:40
답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.